Orientations and detachments of graphs with prescribed degrees and connectivity
Orientations and detachments of graphs with prescribed degrees and connectivity
复制标题
具有规定度数和连通性的图的方向和分离
DOI：
10.1016/j.disopt.2014.02.003
复制
发表时间：
2014
影响因子：
1.1
通讯作者：
Satoru Iwata and Tibor Jordan
中科院分区：
文献类型：
--
作者：
Matsuo Konagaya;Tetsuo Asano;Satoru Iwata and Tibor Jordan
我们给出了一个图的方向有k个边不相交的树形根于指定的顶点s，且在每个顶点的in度上有下界和上界的充分必要条件。该结果用于导出具有包含k个边不相交生成树的分离的图的表征。还描述了寻找这些方向和分离的有效算法。特别地，本文提供了一种在O （n m）时间内找到连接（无环路）分离的算法，改进了之前的最佳运行时间界限，其中n和m分别表示顶点和边的数量。
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 (n m) time, improving on the previous best running time bound, where n and m denote the numbers of vertices and edges, respectively.