Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141443 | Discrete Optimization | 2014 | 8 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Satoru Iwata, Tibor Jordán,