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) ) that this problem is NP-complete even if r1 = r2. As a special case, it is only known (Bang-Jensen (1991) ) 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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications