Arc-disjoint in-trees in directed graphs

Naoyuki Kamiyama; Naoki Katoh; Atsushi Takizawa

Arc-disjoint in-trees in directed graphs

Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a directed graph D = (V, A) and a set of specified vertices S = {s₁,... , S_d} ⊆ V with |S| = d and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition that there exist Σ_si∈S f(s_i) arc-disjoint in-trees denoted by T_i,1,T _i,2,...,T_i,f(s_i) for every i = 1,...,d such that T_i,1,..., T_i,f(s_i) are rooted at s _i and each T_i,j spans 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.

Original language	English
Title of host publication	Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	518-526
Number of pages	9
Publication status	Published - Dec 1 2008
Externally published	Yes
Event	19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States Duration: Jan 20 2008 → Jan 22 2008

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other	19th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	San Francisco, CA
Period	1/20/08 → 1/22/08

All Science Journal Classification (ASJC) codes

Software
Mathematics(all)

Cite this

@inproceedings{7dd9c8152fd74b319828908b1ce1ed0d,

title = "Arc-disjoint in-trees in directed graphs",

abstract = "Given a directed graph D = (V, A) and a set of specified vertices S = {s1,... , Sd} ⊆ V with |S| = d and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition that there exist Σsi∈S f(si) arc-disjoint in-trees denoted by Ti,1,T i,2,...,Ti,f(si) for every i = 1,...,d such that Ti,1,..., Ti,f(si) are rooted at s i and each Ti,j spans vertices from which si 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.",

author = "Naoyuki Kamiyama and Naoki Katoh and Atsushi Takizawa",

year = "2008",

month = dec,

day = "1",

language = "English",

isbn = "9780898716474",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

pages = "518--526",

booktitle = "Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "19th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 20-01-2008 Through 22-01-2008",

}

TY - GEN

T1 - Arc-disjoint in-trees in directed graphs

AU - Kamiyama, Naoyuki

AU - Katoh, Naoki

AU - Takizawa, Atsushi

PY - 2008/12/1

Y1 - 2008/12/1

N2 - Given a directed graph D = (V, A) and a set of specified vertices S = {s1,... , Sd} ⊆ V with |S| = d and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition that there exist Σsi∈S f(si) arc-disjoint in-trees denoted by Ti,1,T i,2,...,Ti,f(si) for every i = 1,...,d such that Ti,1,..., Ti,f(si) are rooted at s i and each Ti,j spans vertices from which si 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.

AB - Given a directed graph D = (V, A) and a set of specified vertices S = {s1,... , Sd} ⊆ V with |S| = d and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition that there exist Σsi∈S f(si) arc-disjoint in-trees denoted by Ti,1,T i,2,...,Ti,f(si) for every i = 1,...,d such that Ti,1,..., Ti,f(si) are rooted at s i and each Ti,j spans vertices from which si 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.

UR - http://www.scopus.com/inward/record.url?scp=48249147916&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=48249147916&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:48249147916

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 518

EP - 526

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -

Arc-disjoint in-trees in directed graphs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this