Computing minimum-weight perfect matchings

We make several observations on the implementation of Edmonds' blossom algo rithm for solving minimum-weight perfect-matching problems and we present c omputational 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 th e use of multiple search trees with an individual dual-change epsilon for e ach tree. As a benchmark of the algorithm's performance, solving a 100,000- node geometric instance on a 200 Mhz Pentium-Pro computer takes approximate ly 3 minutes.