Blossom V

Blossom V: A new implementation of a minimum cost perfect matching algorithm 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 W. Cook and A. Rohe [INFORMS J. Comput. 11, No. 2, 138–148 (1999; Zbl 1040.90539)] 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 [loc. cit.] and K. Mehlhorn and G. Schäfer [ACM J. Exp. Algorithm. 7, Spec. Iss., Article 4, 19 p., electronic only (2002; Zbl 1083.68650)], 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


References in zbMATH (referenced in 12 articles , 1 standard article )

Showing results 1 to 12 of 12.
Sorted by year (citations)

  1. Marzouk, Ahmed M.; Moreno-Centeno, Erick; Üster, Halit: A branch-and-price algorithm for solving the Hamiltonian $p$-median problem (2016)
  2. Williamson, Matthew; Eirinakis, Pavlos; Subramani, K.: Fast algorithms for the undirected negative cost cycle detection problem (2016)
  3. Pereira, André G.; Ritt, Marcus; Buriol, Luciana S.: Optimal Sokoban solving using pattern databases with specific domain knowledge (2015)
  4. Wimer, Shmuel: Easy and difficult exact covering problems arising in VLSI power reduction by clock gating (2014)
  5. Stockbridge, Rebecca; Bayraksan, Güzin: A probability metrics approach for reducing the bias of optimality gap estimators in two-stage stochastic linear programming (2013)
  6. Wimer, Shmuel: On optimal flip-flop grouping for VLSI power minimization (2013)
  7. Kirlik, Gokhan; Sipahioglu, Aydin: Capacitated arc routing problem with deadheading demands (2012)
  8. Liers, F.; Pardella, G.: Partitioning planar graphs: a fast combinatorial approach for max-cut (2012)
  9. Bilò, Davide; Forlizzi, Luca; Proietti, Guido: Approximating the metric TSP in linear time (2011)
  10. Grady, Leo J.; Polimeni, Jonathan R.: Discrete calculus. Applied analysis on graphs for computational science (2010)
  11. Kolmogorov, Vladimir: Blossom V: A new implementation of a minimum cost perfect matching algorithm (2009)
  12. Cook, William; Rohe, André: Computing minimum-weight perfect matchings. (1999)