Name
Title | ||
|---|---|---|
Arc-Disjoint In- and Out-Branchings With the Same Root in Locally Semicomplete Digraphs |
Abstract | ||
|---|---|---|
AbstractDeciding whether a digraph contains a pair of arc-disjoint in- and out-branchings rooted at a specified vertex is a well-known NP-complete problem as proved by Thomassen, see . This problem has been shown to be polynomial time solvable for semicomplete digraphs and for quasi-transitive digraphs . In this article, we study the problem for locally semicomplete digraphs. We characterize locally semicomplete digraphs that contain a pair of arc-disjoint in- and out-branchings rooted at a specified vertex. Our proofs are constructive and imply the existence of a polynomial time algorithm for finding the desired branchings when they exist. Our results generalizes those from for semicomplete digraphs and solves an open problem from . |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/jgt.21786 | Periodicals |
Keywords | Field | DocType |
Locally semicomplete digraph,structure of locally semicomplete digraphs,arc-disjoint in- and out-branchings,arc-contraction,polynomial time algorithm | Discrete mathematics,Topology,Combinatorics,Arc (geometry),Open problem,Disjoint sets,Vertex (geometry),Constructive,Mathematical proof,Time complexity,Mathematics,Digraph | Journal |
Volume | Issue | ISSN |
77 | 4 | 0364-9024 |
Citations | PageRank | References |
1 | 0.37 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jørgen Bang-Jensen | 1 | 9 | 2.01 |
| Jing Huang | 2 | 3 | 1.15 |