---
_id: '2932'
abstract:
- lang: eng
  text: |+
    We describe a new implementation of the Edmonds’s 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 (INFORMS J Comput 11(2):138–148, 1999) and the use of priority queues. We achieve this by maintaining an auxiliary graph whose nodes correspond to alternating trees in the Edmonds’s 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 (INFORMS J Comput 11(2):138–148, 1999) and Mehlhorn and Schäfer (J Algorithmics Exp (JEA) 7:4, 2002), 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.

author:
- first_name: Vladimir
  full_name: Vladimir Kolmogorov
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: 'Kolmogorov V. Blossom V: A new implementation of a minimum cost perfect matching
    algorithm. <i>Mathematical Programming Computation</i>. 2009;1(1):43-67. doi:<a
    href="https://doi.org/10.1007/s12532-009-0002-8">10.1007/s12532-009-0002-8</a>'
  apa: 'Kolmogorov, V. (2009). Blossom V: A new implementation of a minimum cost perfect
    matching algorithm. <i>Mathematical Programming Computation</i>. Springer. <a
    href="https://doi.org/10.1007/s12532-009-0002-8">https://doi.org/10.1007/s12532-009-0002-8</a>'
  chicago: 'Kolmogorov, Vladimir. “Blossom V: A New Implementation of a Minimum Cost
    Perfect Matching Algorithm.” <i>Mathematical Programming Computation</i>. Springer,
    2009. <a href="https://doi.org/10.1007/s12532-009-0002-8">https://doi.org/10.1007/s12532-009-0002-8</a>.'
  ieee: 'V. Kolmogorov, “Blossom V: A new implementation of a minimum cost perfect
    matching algorithm,” <i>Mathematical Programming Computation</i>, vol. 1, no.
    1. Springer, pp. 43–67, 2009.'
  ista: 'Kolmogorov V. 2009. Blossom V: A new implementation of a minimum cost perfect
    matching algorithm. Mathematical Programming Computation. 1(1), 43–67.'
  mla: 'Kolmogorov, Vladimir. “Blossom V: A New Implementation of a Minimum Cost Perfect
    Matching Algorithm.” <i>Mathematical Programming Computation</i>, vol. 1, no.
    1, Springer, 2009, pp. 43–67, doi:<a href="https://doi.org/10.1007/s12532-009-0002-8">10.1007/s12532-009-0002-8</a>.'
  short: V. Kolmogorov, Mathematical Programming Computation 1 (2009) 43–67.
date_created: 2018-12-11T12:00:25Z
date_published: 2009-07-01T00:00:00Z
date_updated: 2021-01-12T07:00:47Z
day: '01'
doi: 10.1007/s12532-009-0002-8
extern: 1
intvolume: '         1'
issue: '1'
month: '07'
page: 43 - 67
publication: Mathematical Programming Computation
publication_status: published
publisher: Springer
publist_id: '3804'
quality_controlled: 0
status: public
title: 'Blossom V: A new implementation of a minimum cost perfect matching algorithm'
type: journal_article
volume: 1
year: '2009'
...
...