This Blossom V software implements an algorithm that solves the following problem:Given an undirected weighted graph, it computes a perfect matching of minimum cost.
This Blossom V software implements an algorithm that solves the following problem:
Given an undirected weighted graph, it computes a perfect matching of minimum cost.
The implemented algorithm is described in the following paper:
“Blossom V: A new implementation of a minimum cost perfect matching algorithm”
Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.
On many types of problems Blossom V outperforms previous implementations of Cook and Rohe (“Blossom IV”) and of Mehlhorn and Schaefer, sometimes by an order of magnitude. The key feature of Blossom V that gives this improvement is a combination of two ideas that previously were used only separately: (i) a flexible dual update strategy and (ii) a use of priority queues.
The software assumes that the graph contains at least one perfect matching; if it is not the case then the behaviour is undefined. The code can also be used for computing a maximum (non-perfect) matching: the latter problem can be reduced to a perfect matching problem via a reduction described in section 1.5.1 of Guido Schäfer's Master's thesis “Weighted matchings in general graphs”. This reduction doubles the size of the graph.
By default, the code uses weights of type “int”. While it is possible to change it to “double”, it is not recommended: rounding errors may then lead to unexpected behaviour, such as non-termination. Internally, small numbers are represented as differences of big numbers, so with a floating point precision the code becomes unstable.
Vladimir Kolmogorov joined UCL in 2005 as Lecturer in the Department of Computer Science. He moved to IST, Austria in 2011 where he holds the position of Assistant Professor.
The software code compiles in:
- Windows with Microsoft Visual C++ compiler
- Kolmogorov (July 2009), Blossom V: A new implementation of a minimum cost perfect matching algorithm, Mathematical Programming Computation (MPC), July 2009, 1(1):43-67
swap_vertical_circlecloud_downloadSupporting documents (0)Additional files may be available once you've completed the transaction for this product. If you've already done so, please log into your account and visit My account / Downloads section to view them.