Accession Number:
ADA011840
Title:
On Edge-Disjoint Branchings
Descriptive Note:
Technical rept.
Corporate Author:
CORNELL UNIV ITHACA NY DEPT OF OPERATIONS RESEARCH
Personal Author(s):
Report Date:
1975-06-01
Pagination or Media Count:
13.0
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. 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.
Descriptors:
Subject Categories:
- Operations Research