Blossom IV

Computing minimum-weight perfect matchings. We make several observations on the implementation of Edmonds’ blossom algorithm for solving minimum-weight perfect-matching problems and we present computational results for geometric problem instances ranging in size from 1,000 nodes up to 5,000,000 nodes. A key feature in our implementation is the use of multiple search trees with an individual dual-change $varepsilon$ for each tree. As a benchmark of the algorithm’s performance, solving a 100,000-node geometric instance on a 200 Mhz Pentium-Pro computer takes approximately 3 minutes.


References in zbMATH (referenced in 31 articles )

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

1 2 next

  1. Williamson, Matthew; Eirinakis, Pavlos; Subramani, K.: Fast algorithms for the undirected negative cost cycle detection problem (2016)
  2. Briskorn, Dirk; Horbach, Andrei: A Lagrangian approach for minimum cost single round robin tournaments (2012)
  3. Delon, J.; Salomon, J.; Sobolevski, A.: Minimum-weight perfect matching for nonintrinsic distances on the line (2012)
  4. Liers, F.; Pardella, G.: Partitioning planar graphs: a fast combinatorial approach for max-cut (2012)
  5. Remacle, J.-F.; Lambrechts, J.; Seny, B.; Marchandise, E.; Johnen, A.; Geuzainet, C.: Blossom-Quad: a non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm (2012)
  6. Rohrmüller, Florian; Wollherr, Dirk; Buss, Martin: MuRoCo: a framework for capability- and situation-aware coalition formation in cooperative multi-robot systems (2012)
  7. Ruth, David M.; Koyak, Robert A.: Nonparametric tests for homogeneity based on non-bipartite matching (2011)
  8. Bordenave, Charles; Gendreau, Michel; Laporte, Gilbert: Heuristics for the mixed swapping problem (2010)
  9. Ruggeri, Mauro R.; Patanè, Giuseppe; Spagnuolo, Michela; Saupe, Dietmar: Spectral-driven isometry-invariant matching of 3D shapes (2010)
  10. Briskorn, D.; Drexl, A.: A branch-and-price algorithm for scheduling sport leagues (2009)
  11. Kolmogorov, Vladimir: Blossom V: A new implementation of a minimum cost perfect matching algorithm (2009)
  12. Small, Dylan S.; Rosenbaum, Paul R.: Error-free milestones in error prone measurements (2009)
  13. Glickman, Mark E.: Bayesian locally optimal design of knockout tournaments (2008)
  14. Fekete, Sándor P.; Der Veen, Jan C.Van: PackLib$^2$: an integrated library of multi-dimensional packing problems (2007)
  15. Toroslu, Ismail H.; Üçoluk, Göktürk: Incremental assignment problem (2007)
  16. Diaz-Gutierrez, Pablo; Bhushan, Anusheel; Gopi, M.; Pajarola, Renato: Single-strips for fast interactive rendering (2006)
  17. Glickman, Mark E.; Jensen, Shane T.: Adaptive paired comparison design (2005)
  18. Caprara, Alberto; Lodi, Andrea; Rizzi, Romeo: On $d$-threshold graphs and $d$-dimensional bin packing (2004)
  19. Walshaw, Chris: Multilevel refinement for combinatorial optimisation problems (2004)
  20. Drake, Doratha E.; Hougardy, Stefan: A simple approximation algorithm for the weighted matching problem (2003)

1 2 next