Fachbereich 3 Mathematik Cardinality Matching: Heuristic Search for Augmenting Paths Cardinality Matching: Heuristic Search for Augmenting Paths
Fachbereich 3 Mathematik Cardinality Matching: Heuristic Search for Augmenting Paths Cardinality Matching: Heuristic Search for Augmenting Paths
复制标题
Fachbereich 3 Mathematik 基数匹配：增强路径的启发式搜索 基数匹配：增强路径的启发式搜索
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Rolf H Mm Ohring
中科院分区：
文献类型：
--
作者：
Rolf H M Ohring;Matthias M Uller{hannemann;Rolf H Mm Ohring
给出了基数匹配问题的一种新启发式，并与不同的贪婪启发式进行了比较。改进的深度优先搜索用于启发式搜索相对于给定匹配的增广路径。在对随机生成的图进行大量测试运行时，我们的启发式通常会给出最佳解决方案，并且只有在极少数情况下，我们观察到的基数比最佳解决方案小一。已知在基数匹配的 DIMACS 挑战中困难的稀疏图的计算结果表明，这种启发式与 Karp 和 Sipser KS81] 的启动过程相结合比许多有效的精确算法快得多。最优性证明可以通过严格上限或通过运行 Micali 和 Vazirani MV80] 算法的一个阶段来获得。我们的方法可以用作预处理器来加速精确算法。
A new heuristic for the cardinality matching problem is given and compared with diierent greedy heuristics. A modiied depth rst search is used to search heuristically for an augmenting path with respect to a given matching. In a large number of test-runs on randomly generated graphs, our heuristic usually gave optimal solutions, and only in rare cases we observed cardinalities one less than the optimal ones. Computational results on sparse graphs which are known to be diicult from the DIMACS challenge on cardinality matching show that this heuristic combined with a starting procedure of Karp and Sipser KS81] is much faster than many eecient exact algorithms. A proof of optimality was either obtained by a tight upper bound or by running one phase of the algorithm of Micali and Vazirani MV80]. Our method can be used as a preprocessor to speed up exact algorithms.