Arc-disjoint in-trees in directed graphs |
| |
Authors: | Naoyuki Kamiyama Naoki Katoh Atsushi Takizawa |
| |
Institution: | (1) Department of Architecture and Architectural Engineering, Kyoto University, Kyotodaigaku-Katsura, Nishikyo-ku, Kyoto 615-8540, Japan |
| |
Abstract: | Given a directed graph D = (V,A) with a set of d specified vertices S = {s
1,…, s
d
} ⊆ V and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Σ
i=1
d
f(s
i
) arc-disjoint in-trees denoted by T
i,1,T
i,2,…, for every i = 1,…,d such that T
i,1,…, are rooted at s
i
and each T
i,j
spans the vertices from which s
i
is reachable. This generalizes the result of Edmonds 2], i.e., the necessary and sufficient condition that for a directed
graph D=(V,A) with a specified vertex s∈V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds 1] to the one in our case.
Supported by JSPS Research Fellowships for Young Scientists.
Supported by the project New Horizons in Computing, Grand-in-Aid for Scientific Research on Priority Areas, MEXT Japan. |
| |
Keywords: | Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000) 05C70 05C40 |
本文献已被 SpringerLink 等数据库收录! |
|