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.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element

References in zbMATH (referenced in 36 articles )

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

1 2 next

  1. Domingo Colomer, Laia; Skotiniotis, Michalis; Muñoz-Tapia, Ramon: Reinforcement learning for optimal error correction of toric codes (2020)
  2. Rujeerapaiboon, Napat; Schindler, Kilian; Kuhn, Daniel; Wiesemann, Wolfram: Size matters: cardinality-constrained clustering and outlier detection via conic optimization (2019)
  3. Wøhlk, Sanne; Laporte, Gilbert: Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs (2017)
  4. Xu, Zhou; Rodrigues, Brian: An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem (2017)
  5. Williamson, Matthew; Eirinakis, Pavlos; Subramani, K.: Fast algorithms for the undirected negative cost cycle detection problem (2016)
  6. Briskorn, Dirk; Horbach, Andrei: A Lagrangian approach for minimum cost single round robin tournaments (2012)
  7. Delon, J.; Salomon, J.; Sobolevski, A.: Minimum-weight perfect matching for nonintrinsic distances on the line (2012)
  8. Liers, F.; Pardella, G.: Partitioning planar graphs: a fast combinatorial approach for max-cut (2012)
  9. 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)
  10. Rohrmüller, Florian; Wollherr, Dirk; Buss, Martin: MuRoCo: a framework for capability- and situation-aware coalition formation in cooperative multi-robot systems (2012)
  11. Ruth, David M.; Koyak, Robert A.: Nonparametric tests for homogeneity based on non-bipartite matching (2011)
  12. Bordenave, Charles; Gendreau, Michel; Laporte, Gilbert: Heuristics for the mixed swapping problem (2010)
  13. Ruggeri, Mauro R.; Patanè, Giuseppe; Spagnuolo, Michela; Saupe, Dietmar: Spectral-driven isometry-invariant matching of 3D shapes (2010) ioport
  14. Briskorn, D.; Drexl, A.: A branch-and-price algorithm for scheduling sport leagues (2009)
  15. Hougardy, Stefan: Linear time approximation algorithms for degree constrained subgraph problems (2009)
  16. Kolmogorov, Vladimir: Blossom V: A new implementation of a minimum cost perfect matching algorithm (2009)
  17. Small, Dylan S.; Rosenbaum, Paul R.: Error-free milestones in error prone measurements (2009)
  18. Glickman, Mark E.: Bayesian locally optimal design of knockout tournaments (2008)
  19. Fekete, Sándor P.; Der Veen, Jan C. Van: PackLib(^2): an integrated library of multi-dimensional packing problems (2007)
  20. Toroslu, Ismail H.; Üçoluk, Göktürk: Incremental assignment problem (2007)

1 2 next