Covering Directed Graphs by In-Trees
Given a directed graph D=(V, A) with a set of d specified vertices S=s1,..., Sd C V and a function f: S →Z+ where Z+ denotes the set of nonnegative integers, we consider the problem which asks whether there exist ∑i=1d f(si) in-trees denoted by Ti,1, Ti,2,...,Ti,f(si) for every i=1,..., d such that Ti,1,..., Ti,f(Si) are rooted at Si, each Ti,j spans vertices from which si is reachable and the union of all arc sets of Ti,j for i=1,..., d and j =1,..., f(si) 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=1d f (si) 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.
Naoyuki Kamiyama Naoki Katoh
Department of Architecture and Architectural Engineering,Kyoto University, Kyotodaigaku-Katsura, Nis Department of Architecture and Architectural Engineering, Kyoto University, Kyotodaigaku-Katsura, Ni
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
444-457
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）