Given a directed graph D = (V, A) with a set of d specified vertices S = {s(1), . . . , s(d)} subset of V and a function f : S -> N where N denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Sigma(d)(i=1) f(s(i)) arc-disjoint in-trees denoted by T-i,T-1,T-i,T-2, . . . ,T-i,T-f(si) for every i = 1, . . . ,d such that T-i,T-1, . . . , T-i,T-f(si) are rooted at s(i) and each T-i,T-j spans the 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 is an element of 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.
展开▼
