Covering directed graphs by in-trees

ISSN： 1382-6905

Source： Journal of Combinatorial Optimization, Vol.21, Iss.1, 2011-01, pp. : 2-18

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Given a directed graph D=(V,A) with a set of d specified vertices S={s ₁,…,s _d}⊆V and a function f : S→ where denotes the set of positive integers, we consider the problem which asks whether there exist ∑ _i=1^d f(s _i) in-trees denoted by $T_{i,1},T_{i,2},ldots,T_{i,f(s_{i})}$ for every i=1,…,d such that $T_{i,1},ldots,T_{i,f(s_{i})}$ are rooted at s _i, each T _i,j spans vertices from which s _i is reachable and the union of all arc sets of T _i,j for i=1,…,d and j=1,…,f(s _i) covers A. In this paper, we prove that such set of in-trees covering A can be found by using an algorithm for the weighted matroid intersection problem in time bounded by a polynomial in ∑ _i=1^d f(s _i) and the size of D. Furthermore, for the case where D is acyclic, we present another characterization of the existence of in-trees covering A, and then we prove that in-trees covering A can be computed more efficiently than the general case by finding maximum matchings in a series of bipartite graphs.