Computing Maximum-Cardinality Matchings in Sparse General Graphs.
John D. Kececioglu, A. Justin Pecqueur · 1998
We give an experimental study of a new O(mn ff(m; n))-time implementation of Edmonds' algorithm for a maximum-cardinality matching in a sparse general graph of n vertices and m edges. The implementation incorporates several optimizations resulting from a depth-first order to search for augmenting paths, and we study the iteraction between four heuristics, each with the potential to significantly speed up the code in practice, through experiments with all sixteen possible variants. The experiments indicate that the simplest heuristic, an earlytermination test for the depth-first search, results in the greatest performance gain, and yields an implementation that on graphs with large degree actually finds an optimal solution in less time than a standard greedy heuristic. The resulting code appears to be the fastest among those publicly available on the classes of random, k-regular, union-of-k-cycle, and Euclidean k-nearest-neighbor graphs for tests with up to 100,000 vertices and 500,000 edges with average degree from 1 to 10, achieving a maximum speedup of 50 over the two LEDA codes, and 4 and 350 over two of the DIMACS implementation challenge codes, while never taking longer than these implementations.