Premium
On edge‐disjoint branchings
Author(s) -
Fulkerson D. R.,
Harding G. C.
Publication year - 1976
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230060203
Subject(s) - computer science , disjoint sets , citation , library science , combinatorics , mathematics
: 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.