Orientations and Detachments of Graphs with Prescribed Degrees and Connectivity

Satoru Iwata, Tibor Jordán


We give a necessary and sufficient condition for a graph to have an orientation that has $k$ edge-disjoint arborescences rooted at a designated vertex $s$ subject to lower and upper bounds on the in-degree at each vertex. The result is used to derive a characterization of graphs having a detachment that contains $k$ edge-disjoint spanning trees. Efficient algorithms for finding those orientations and detachments are also described. In particular, the paper provides an algorithm for finding a connected (loopless) detachment in $O(nm)$ time, improving on the previous best running time bound, where $n$ and $m$ denote the numbers of vertices and edges, respectively.

Bibtex entry:

AUTHOR = {Iwata, Satoru and Jord{\'a}n, Tibor},
TITLE = {Orientations and Detachments of Graphs with Prescribed Degrees and Connectivity},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2013},
NUMBER = {TR-2013-01}

Last modification: 5.6.2018. Please email your comments to Tamás Király!