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 33 articles )

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

1 2 next

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

1 2 next