Weighted Matchings in General Graphs

research over several decades. In 1965, Edmonds invented the famous blossom shrinking
approach, which enables to compute a weighted matching in polynomial time $O(n^2 m)$.
Since then, the theoretical running time has been successively improved from $O(n^2 m)$,
$O(n^3)$ (Lawler [76] and Gabow [74]), $O(nm \log n)$ (Galil et al. [86]) up to
$O(n(m + n \log n))$ (Gabow [90]).
The algorithms suggested by Galil et al. [86] and by Gabow [90] mainly achieve a better
asymptotic time bound by using sophisticated data structures. However, the most efficient
codes currently available are based on either the $O(n^2 m)$ or the $O(n^3)$ approach and
only use very simple data structures. It has been an open question whether or not
sophisticated data structures will help in practice.

We will sketch the key ideas underlying our $O(nm \log n)$ implementation and present some
experimental results comparing our implementation with the currently most efficient code,
called Blossom IV, due to Cook and Rohe [97].