Blossom IV

swMATH ID: 4781
Software Authors: Cook, William; Rohe, André
Description: Computing minimum-weight perfect matchings. 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 \(varepsilon\) 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.
Homepage: http://www2.isye.gatech.edu/~wcook/blossom4/
Keywords: Edmonds blossom algorithm; computational algorithms; perfect matchings; networks/graphs; minimum-weight
Related Software: TSPLIB; Blossom V; DIMACS; LEDA; MESHPART; CPLEX; Algorithm 97; MuRoCo; OGDF; GraphBase; Blossom-Quad; Q-Morph; Gmsh; EMD; optmatch; Triangle; VLSI; Boost; Concorde; Boost C++ Libraries
Cited in: 34 Publications

Citations by Year