A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
Suppose that we are given a directed graph D = (V, A) with specified vertices r(1), r(2) is an element of V. this paper, we consider the problem of discerning the existence of a pair of arc-disjoint spanning in-arborescence rooted at r(1) and out-arborescence rooted at r(2), and finding such arborescences if they exist. It is known (Bang-Jensen (1991) [1]) that this problem is NP-complete even if r(1) = r(2). 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. (C) 2009 Elsevier B.V. All rights reserved.
arborescence directed graph graph algorithms packing