A Generalization of Edmonds' Matching and Matroid Intersection Algorithms
A Generalization of Edmonds' Matching and Matroid Intersection Algorithms
复制标题
Edmonds 匹配和拟阵交集算法的推广
DOI：
10.1007/3-540-47867-1_2
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
R. Weismantel
中科院分区：
文献类型：
--
作者：
Bianca Spille;R. Weismantel
独立路径匹配问题是匹配问题和拟阵交问题的一种常见推广。坎宁安（Cunningham）和吉伦（Geelen）证明了通过椭球法该问题可在多项式时间内求解。我们针对其无权版本提出了一个多项式时间的组合算法，该算法推广了基数匹配问题和拟阵交问题的已知组合算法。
The independent path-matching problem is a common generalization of the matching problem and the matroid intersection problem. Cunningham and Geelen proved that this problem is solvable in polynomial time via the ellipsoid method. We present a polynomial-time combinatorial algorithm for its unweighted version that generalizes the known combinatorial algorithms for the cardinality matching problem and the matroid intersection problem.