| Article ID: | iaor20003003 |
| Country: | United States |
| Volume: | 11 |
| Issue: | 2 |
| Start Page Number: | 138 |
| End Page Number: | 148 |
| Publication Date: | Mar 1999 |
| Journal: | INFORMS Journal On Computing |
| Authors: | Cook William, Rohe Andr |
| Keywords: | networks |
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 ε 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.