| Arc-disjoint in-trees in directed graphs (2008) | |||||||||||
Abstract | |||||||||||
| Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Dis crete Algorithms, San Francisco, CA, January 20-22, 2008 ; This symposium was sponsored by the ACM Special Interest Group on Algorithms and Computation Theory and the SIAM Activity Group on Discrete Mathematics. Given a directed graph D = (V, A) and a set of specified vertices S = {s1,…,sd} ⊆ V with |S| = d and a function f: S → N where N denotes the set of natural numbers, we present a necessary and sufficient condition that there exist Σsi ε arc-disjoint in-trees denoted by Ti,1,Ti,2,…,Tif (si) for every i = 1,…,d such that Ti,1,…, Ti,f(si) are rooted at si and each Ti,j spans vertices from which si is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graph D = (V,A) with a specified vertex s ε V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case. | |||||||||||
Publication details | |||||||||||
| |||||||||||