On Edge-Disjoint Branchings
CORNELL UNIV ITHACA NY DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
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. Tarjans 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 Tarjans algorithm works.
- Operations Research