| Covering Directed Graphs by In-Trees (Computing and Combinatorics) (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Computing and Combinatorics : 14th annual international conference, COCOON 2008, Dalian, China, June 27-29, 2008 : (Lecture notes in computer science ; 5092). The 14th Annual International Computing and Combinatorics Conference (COCOON 2008). Given a directed graph D = (V,A) with a set of d specified vertices S = {s 1,...,s d } ⊆ V and a function where ℤ + denotes the set of non-negative integers, we consider the problem which asks whether there exist in-trees denoted by for every i = 1,...,d such that 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 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. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||