Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
复制标题
保留和增加混合图中的局部边连通性
DOI：
10.1137/s0036142993226983
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
B. Jackson
中科院分区：
文献类型：
--
作者：
J. Bang;A. Frank;B. Jackson
概括和统一W. Mader的早期结果以及A. Frank和B. Jackson，我们证明了两个有关混合图的分裂定理。通过调用这些定理，我们获得最小数量的新边缘数量的最小数量的新边缘，以使所得图满足局部边缘连接处方。埃德蒙兹（Edmonds）关于分离植物的定理的扩展也可以推导出新的充分条件，以解决digraphs中边缘 - 局部路径问题的可溶性。该方法引起了相应优化问题的强烈多项式算法。
Generalizing and unifying earlier results of W. Mader, and A. Frank and B. Jackson, we prove two splitting theorems concerning mixed graphs. By invoking these theorems we obtain min-max formulae for the minimum number of new edges to be added to a mixed graph so that the resulting graph satisfies local edge-connectivity prescriptions. An extension of Edmonds's theorem on disjoint arborescences is also deduced along with a new sufficient condition for the solvability of the edge-disjoint paths problem in digraphs. The approach gives rise to strongly polynomial algorithms for the corresponding optimization problems.