Edmonds' disjoint arborescences theorem
From Egres Open
Theorem (Edmonds)[1] Let D=(V,A) be a digraph with a designated root node r. D contains k edge-disjoint spanning arborescences rooted at r if and only if [math]\varrho(X)\geq k[/math] for each nonempty [math]X\subseteq V-r[/math].
The following stronger version also holds:
Theorem (Edmonds)[2] Let D=(V,A) be a digraph with arborescences [math]F_1,\ldots,F_k[/math] rooted at r. Then there exist k edge-disjoint spanning arborescences [math]H_1,\ldots,H_k[/math] rooted at r with [math]F_i\subseteq H_i[/math] if and only if each nonempty subset X of V is entered by at least as many arc as there exist i with [math]F_i[/math] disjoint from X.
References
- ↑ J. Edmonds, Submodular functions, matroids, and certain polyhedra, Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications (R. Guy, H. Hanani, N. Sauer and J. Schoenheim, eds., Gordon and Breach, New York, 1970), pp. 69--87; also in: Combinatorial Optimization—Eureka, You Shrink! (M. Juenger, G. Reinelt, and G. Rinaldi, eds., Lecture Notes in Computer Science 2570, Springer, Berlin, 2003), pp. 11--26. DOI link
- ↑ J. Edmonds, Edge-disjoint branchings. In: B. Rustin, Editor, Combinatorial Algorithms, Academic Press, New York (1973), pp. 91--96.
