TR-2013-01

Orientations and Detachments of Graphs with Prescribed Degrees and Connectivity

Satoru Iwata, Tibor Jordán

Published in:
Discrete Optimization, Volume 12, 2014, Pages 121-128. DOI link

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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2013},
NUMBER	=	{TR-2013-01}

}