A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph

Kristóf Bérczi; Satoru Fujishige; Naoyuki Kamiyama

doi:10.1016/j.ipl.2009.09.004

A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph

Kristóf Bérczi, Satoru Fujishige, Naoyuki Kamiyama

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

Abstract

Suppose that we are given a directed graph D = (V, A) with specified vertices r₁, r₂ ∈ V. In this paper, we consider the problem of discerning the existence of a pair of arc-disjoint spanning in-arborescence rooted at r₁ and out-arborescence rooted at r₂, and finding such arborescences if they exist. It is known (Bang-Jensen (1991) [1]) that this problem is NP-complete even if r₁ = r₂. As a special case, it is only known (Bang-Jensen (1991) [1]) that this problem in a tournament can be solved in polynomial time. In this paper, we give a linear-time algorithm for this problem in a directed acyclic graph. We also consider an extension of our problem to the case where we have multiple roots for in-arborescences and out-arborescences, respectively.

Original language	English
Pages (from-to)	1227-1231
Number of pages	5
Journal	Information Processing Letters
Volume	109
Issue number	23-24
DOIs	https://doi.org/10.1016/j.ipl.2009.09.004
Publication status	Published - Nov 15 2009
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2009.09.004

Cite this

@article{106c3b49158241a380f524a72b58e175,

title = "A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph",

abstract = "Suppose that we are given a directed graph D = (V, A) with specified vertices r1, r2 ∈ V. In this paper, we consider the problem of discerning the existence of a pair of arc-disjoint spanning in-arborescence rooted at r1 and out-arborescence rooted at r2, and finding such arborescences if they exist. It is known (Bang-Jensen (1991) [1]) that this problem is NP-complete even if r1 = r2. As a special case, it is only known (Bang-Jensen (1991) [1]) that this problem in a tournament can be solved in polynomial time. In this paper, we give a linear-time algorithm for this problem in a directed acyclic graph. We also consider an extension of our problem to the case where we have multiple roots for in-arborescences and out-arborescences, respectively.",

author = "Krist{\'o}f B{\'e}rczi and Satoru Fujishige and Naoyuki Kamiyama",

note = "Funding Information: 1 The present research was partly supported by a Grant-in-Aid from the Ministry of Education, Culture, Sports, Science and Technology of Japan.",

year = "2009",

month = nov,

day = "15",

doi = "10.1016/j.ipl.2009.09.004",

language = "English",

volume = "109",

pages = "1227--1231",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "23-24",

}

TY - JOUR

T1 - A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph

AU - Bérczi, Kristóf

AU - Fujishige, Satoru

AU - Kamiyama, Naoyuki

N1 - Funding Information: 1 The present research was partly supported by a Grant-in-Aid from the Ministry of Education, Culture, Sports, Science and Technology of Japan.

PY - 2009/11/15

Y1 - 2009/11/15

N2 - Suppose that we are given a directed graph D = (V, A) with specified vertices r1, r2 ∈ V. In this paper, we consider the problem of discerning the existence of a pair of arc-disjoint spanning in-arborescence rooted at r1 and out-arborescence rooted at r2, and finding such arborescences if they exist. It is known (Bang-Jensen (1991) [1]) that this problem is NP-complete even if r1 = r2. As a special case, it is only known (Bang-Jensen (1991) [1]) that this problem in a tournament can be solved in polynomial time. In this paper, we give a linear-time algorithm for this problem in a directed acyclic graph. We also consider an extension of our problem to the case where we have multiple roots for in-arborescences and out-arborescences, respectively.

AB - Suppose that we are given a directed graph D = (V, A) with specified vertices r1, r2 ∈ V. In this paper, we consider the problem of discerning the existence of a pair of arc-disjoint spanning in-arborescence rooted at r1 and out-arborescence rooted at r2, and finding such arborescences if they exist. It is known (Bang-Jensen (1991) [1]) that this problem is NP-complete even if r1 = r2. As a special case, it is only known (Bang-Jensen (1991) [1]) that this problem in a tournament can be solved in polynomial time. In this paper, we give a linear-time algorithm for this problem in a directed acyclic graph. We also consider an extension of our problem to the case where we have multiple roots for in-arborescences and out-arborescences, respectively.

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

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

U2 - 10.1016/j.ipl.2009.09.004

DO - 10.1016/j.ipl.2009.09.004

M3 - Article

AN - SCOPUS:70350020745

SN - 0020-0190

VL - 109

SP - 1227

EP - 1231

JO - Information Processing Letters

JF - Information Processing Letters

IS - 23-24

ER -

A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this