Publikationer pr. år
Publikationer pr. år
J. Bang-Jensen*, Y. Wang
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review
An out-branching (Formula presented.) (in-branching (Formula presented.)) in a digraph (Formula presented.) is a connected spanning subdigraph of (Formula presented.) in which every vertex except the vertex (Formula presented.), called the root, has in-degree (out-degree) one. It is well known that there exists a polynomial algorithm for deciding whether a given digraph has (Formula presented.) arc-disjoint out-branchings with prescribed roots ((Formula presented.) is part of the input). In sharp contrast to this, it is already NP-complete to decide if a digraph has one out-branching which is arc-disjoint from some in-branching. A digraph is semicomplete if it has no pair of nonadjacent vertices. A tournament is a semicomplete digraph without directed cycles of length 2. In this paper we give a complete classification of semicomplete digraphs that have an out-branching (Formula presented.) which is arc-disjoint from some in-branching (Formula presented.) where (Formula presented.) are prescribed vertices of (Formula presented.). Our characterization, which is surprisingly simple, generalizes a complicated characterization for tournaments from 1991 by the first author and our proof implies the existence of a polynomial algorithm for checking whether a given semicomplete digraph has such a pair of branchings for prescribed vertices (Formula presented.) and construct a solution if one exists. This confirms a conjecture of Bang-Jensen for the case of semicomplete digraphs.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Journal of Graph Theory |
Vol/bind | 106 |
Udgave nummer | 1 |
Sider (fra-til) | 182-197 |
ISSN | 0364-9024 |
DOI | |
Status | Udgivet - maj 2024 |
Publikation: Afhandling › Ph.d.-afhandling