Computing minimum-weight perfect matchings

被引：141

作者：

Cook, W

Rohe, A

机构：

[1] Rice Univ, Houston, TX 77005 USA

[2] Univ Bonn, Forsch Inst Diskrete Math, D-53115 Bonn, Germany

来源：

INFORMS JOURNAL ON COMPUTING | 1999年 / 11卷 / 02期

关键词：

perfect matchings; networks/graphs; minimum-weight;

D O I：

10.1287/ijoc.11.2.138

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We make several observations on the implementation of Edmonds' blossom algorithm for solving minimum-weight perfect-matching problems and we present computational results for geometric problem instances ranging in size from 1,000 nodes up to 5,000,000 nodes. A key feature In our implementation is the use of multiple search trees with an individual dual-change epsilon for each tree. As a benchmark of the algorithm's performance, solving a 100,000-node geometric instance on a 200 Mhz Pentium-Pro computer takes approximately 3 minutes.

引用

页码：138 / 148

页数：11

共 64 条

[1]

Aho A. V., 1976, SIAM Journal on Computing, V5, P115, DOI 10.1137/0205011

[2]

AKL SG, 1983, J COMBINATORICS INFO, V8, P175

[3]

[Anonymous], 1996, 1 WORKSHOP APPL COMP

[4]

[Anonymous], NETWORK FLOWS MATCHI