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