Orientations and detachments of graphs with prescribed degrees and connectivity

被引：0

作者：

Iwata, Satoru ^{[1
]}

Jordan, Tibor ^{[2
,3
]}

机构：

[1] Univ Tokyo, Dept Math Informat, Tokyo 1138656, Japan

[2] Eotvos Lorand Univ, Dept Operat Res, H-1117 Budapest, Hungary

[3] MTA ELTE Egervary Res Grp Combinatorial Optimizat, Budapest, Hungary

来源：

DISCRETE OPTIMIZATION | 2014年 / 12卷

基金：

匈牙利科学研究基金会;

关键词：

Detachment; Graph; Orientation; Arborescence; Spanning tree;

D O I：

10.1016/j.disopt.2014.02.003

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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

引用

页码：121 / 128

页数：8