Arc-disjoint in-trees in directed graphs

• Kamiyama, Naoyuki

• Katoh, Naoki

• Takizawa, Atsushi

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, …, $$ T_{i, f(s_0 )} $$ for every i = 1, …, d such that T i, 1, …, $$ T_{i, f(s_0 )} $$ 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.

Journal

• Combinatorica

  Combinatorica 29 (2), 197-214, 2009-03

  Springer

Details

• CRID: 1050282810662182528
• NII Article ID: 120002317413
• NII Book ID: AA10439913
• ISSN: 02099683
• HANDLE: 2433/123379
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • CiNii Articles
  • KAKEN