Orientations and detachments of graphs with prescribed degrees and connectivity

Iwata, S. and Jordán, Tibor (2014) Orientations and detachments of graphs with prescribed degrees and connectivity. Discrete Optimization, 12 (1). pp. 121-128. ISSN 1572-5286

Preview

Text OrientationsAndDetachments.pdf Download (389kB) | Preview

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. © 2014 Elsevier B.V. All rights reserved.

Actions (login required)

Edit Item