Naoyuki Kamiyama, Naoki Katoh
COMPUTING AND COMBINATORICS, PROCEEDINGS 5092 444-457 2008年 査読有り
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 -> Z(+) where Z(+) denotes the set of non-negative integers, we consider the problem which asks whether there exist Sigma(d)(i=1) f(s(i)) 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-2, ... , T-i,T-f(si) are rooted at si, each T-i,T-j spans vertices from which s(i) is reachable and the union of all arc sets of T-i,T-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 Sigma(d)(i=1) 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.