A Blossom Algorithm for Maximum Edge-Disjoint T-Paths
A Blossom Algorithm for Maximum Edge-Disjoint T-Paths
复制标题
最大边不相交T路径的Blossom算法
DOI：
10.1137/1.9781611975994.119
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yokoi Yu
中科院分区：
文献类型：
--
作者：
Iwata Satoru;Yokoi Yu
设G =（V，E）是一个具有一个终端集T ∈ V的多重图. G中的一条路称为T-路，如果它的端点是T中的不同顶点，并且没有内部顶点属于T。1978年，马德尔给出了边不相交T-路的最大个数的一个刻画.原来的证明是不建设性的，因此它没有提出一个有效的algorithm.In本文中，我们提供了一个组合的，确定性的算法，找到最大数量的边disjointT-路径。该算法采用增广路径的方法。更具体地说，我们引入了一个新的概念，在辅助标记图中增加行走，以捕获可能的边disjointT-路径的数量增加。为了设计增强行走的搜索过程，我们引入了类似于Edmonds（1965）的匹配问题的开花算法的开花，但它既不是特殊情况，也不是本问题的推广。当搜索过程没有找到增广行走终止时，该算法提供了当前边不相交T-路径的最优性的证书。因此，该算法的正确性论证可作为马德尔关于边不相交T-路定理的另一种直接证明。该算法的运行时间为O（|V| · |E| 2）时间，这比基于线性拟阵奇偶问题的简化的最佳已知确定性算法快得多。
LetG= (V, E) be a multigraph with a setT⊆Vof terminals. A path inGis called aT-path if its ends are distinct vertices inTand no internal vertices belong toT. In 1978, Mader showed a characterization of the maximum number of edge-disjointT-paths. The original proof was not constructive, and hence it did not suggest an efficient algorithm.In this paper, we provide a combinatorial, deterministic algorithm for finding the maximum number of edge-disjointT-paths. The algorithm adopts an augmenting path approach. More specifically, we introduce a novel concept of augmenting walks in auxiliary labeled graphs to capture a possible augmentation of the number of edge-disjointT-paths. To design a search procedure for an augmenting walk, we introduce blossoms analogously to the blossom algorithm of Edmonds (1965) for the matching problem, while it is neither a special case nor a generalization of the present problem. When the search procedure terminates without finding an augmenting walk, the algorithm provides a certificate for the optimality of the current edge-disjointT-paths. Thus the correctness argument of the algorithm serves as an alternative direct proof of Mader's theorem on edge-disjointT-paths. The algorithm runs inO(|V| • |E|2) time, which is much faster than the best known deterministic algorithm based on a reduction to the linear matroid parity problem.
登录
查看更多内容
总成本最小的多流和不相交路径
影响因子：
2.7
作者：
A. Karzanov
通讯作者：
A. Karzanov
马德 I 路径定理的简短证明：319
DOI：
--
发表时间：
2001
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
A. Schrijver
通讯作者：
A. Schrijver
线性拟阵奇偶校验的增广路径算法
DOI：
--
发表时间：
1986
期刊：
Comb.
影响因子：
--
作者：
H. Gabow;Matthias F. Stallmann
通讯作者：
Matthias F. Stallmann
影响因子：
1.1
作者：
Chudnovsky, Maria;Cunningham, William H.;Geelen, Jim
通讯作者：
Geelen, Jim
线性拟阵奇偶校验问题的代数算法
DOI：
10.1145/2601066
发表时间：
2011
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
Ho Yee Cheung;L. Lau;K. M. Leung
通讯作者：
K. M. Leung