On Edge-Disjoint Branchings

Abstract

Edmonds has given a complicated algorithmic proof of a theorem characterizing directed graphs that contain k edge-disjoint branchings having specified root sets. Tarjan has described a conceptually simple and good algorithm for finding such branchings when they exist. Tarjan's algorithm is based on a lemma implicit in Edmonds' results. A simple direct proof of this lemma is given, thereby providing a simpler proof of Edmonds' theorem and a simpler proof that Tarjan's algorithm works.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1975
Accession Number
ADA011840

Entities

People

  • D. R. Fulkerson
  • Gary Harding

Organizations

  • Cornell University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Electrical Engineering
  • Engineering
  • Inclusions
  • Military Research
  • New York
  • Notation
  • Operations Research
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.