TR-2013-01

Orientations and Detachments of Graphs with Prescribed Degrees and Connectivity

Satoru Iwata, Tibor Jordán



Abstract

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:

@techreport{egres-13-01,
AUTHOR = {Iwata, Satoru and Jord{\'a}n, Tibor},
TITLE = {Orientations and Detachments of Graphs with Prescribed Degrees and Connectivity},
NOTE= {{\tt www.cs.elte.hu/egres}},
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!