Blossom V: A new implementation of a minimum cost perfect matching algorithm

Vladimir Kolmogorov.

In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.


Abstract

We describe a new implementation of the Edmonds' algorithm for computing a perfect matching of minimum cost, to which we refer as Blossom V. A key feature of our implementation is a combination of two ideas that were shown to be effective for this problem: the "variable dual updates" approach of Cook and Rohe [8] and the use of priority queues. We achieve this by maintaining an auxiliary graph whose nodes correspond to alternating trees in the Edmonds' algorithm. While our use of priority queues does not improve the worst-case complexity, it appears to lead to an efficient technique. In the majority of our tests Blossom V outperformed previous implementations of Cook and Rohe [8] and of Mehlhorn and Schaefer [23], sometimes by an order of magnitude. We also show that for large VLSI instances it is beneficial to update duals by solving a linear program, contrary to a conjecture by Cook and Rohe.


Links

The original publication is available at the Springer website. Differently formatted version: [.pdf] [.ps]
[implementation]

Note, the Springer version has a typo in section 3, "Maintaining dual variables": the signs in the equations for variables "yv" for exterior nodes should be flipped. Thanks to Nic Schraudolph for pointing out this and some other typos.