2008/02/20 by Naoyuki Kamiyama, Kamiyama, Naoyuki, Naoki Katoh +1
Computer Science · Engineering · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.0802.2755
openalex publication_date 2008/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a directed graph D=(V,A) with a set of d specified vertices S=\s1,...,sd\⊆ V and a function f\colon S → ℤ+ where ℤ+ denotes the set of non-negative 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=1df(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.