Software Search - zbMATH Open

Blossom IV

swMATH ID:	4781
Software Authors:	Cook, William; Rohe, André
Description:	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.
Homepage:	http://www2.isye.gatech.edu/~wcook/blossom4/
Keywords:	Edmonds blossom algorithm; computational algorithms; perfect matchings; networks/graphs; minimum-weight
Related Software:	TSPLIB; Blossom V; DIMACS; LEDA; MESHPART; CPLEX; Algorithm 97; MuRoCo; OGDF; GraphBase; Blossom-Quad; Q-Morph; Gmsh; EMD; optmatch; Triangle; VLSI; Boost; Concorde; Boost C++ Libraries
Cited in:	34 Publications

all top 5

2	Briskorn, Dirk
2	Caprara, Alberto
2	Glickman, Mark E.
2	Hougardy, Stefan
2	Laporte, Gilbert
2	Müller-Hannemann, Matthias
2	Schwartz, Alexander
2	Walshaw, Chris H.
1	Bečka, Martin
1	Bordenave, Charles
1	Buss, Martin
1	Cook, William John
1	Delon, Julie
1	Derigs, Ulrich
1	Domingo Colomer, Laia
1	Drake, Doratha E.
1	Drexl, Andreas
1	Eirinakis, Pavlos
1	Fang, Shu-Cherng
1	Fekete, Sándor P.
1	Gendreau, Michel
1	Geuzainet, C.
1	Horbach, Andrei
1	Jensen, Shane T.
1	Johnen, Amaury
1	Johnson, David Stifler
1	Kleywegt, Anton J.
1	Kolmogorov, Vladimir
1	Koyak, Robert A.
1	Kuhn, Daniel
1	Lambrechts, Jonathan
1	Lancia, Giuseppe G.
1	Liers, Frauke
1	Lodi, Andrea
1	Marchandise, Emilie
1	McGeoch, Lyle A.
1	Medaglia, Andrés L.
1	Mehlhorn, Kurt
1	Muñoz-Tapia, Ramon
1	Ng, See-Kiong
1	Nori, Vijay S.
1	Okša, Gabriel
1	Pardella, Gregor Leszek
1	Remacle, Jean-François
1	Rizzi, Romeo
1	Rodrigues, Brian
1	Rohe, André
1	Rohrmüller, Florian
1	Rosenbaum, Paul Richard
1	Rujeerapaiboon, Napat
1	Ruth, David M.
1	Salomon, Julien
1	Savelsbergh, Martin W. P.
1	Schafer, Guido
1	Schindler, Kilian
1	Seny, Bruno
1	Skotiniotis, Michalis
1	Small, Dylan S.
1	Sobolevski, Andrei Nikolaevich
1	Subramani, Krishnan
1	Toroslu, Ismail Hakki
1	Üçoluk, Göktürk
1	Vajteršic, Marián
1	van der Veen, Jan C.
1	Wiesemann, Wolfram
1	Williamson, Matthew
1	Wøhlk, Sanne
1	Wollherr, Dirk
1	Xu, Zhou

all top 5

3	Computers & Operations Research
3	European Journal of Operational Research
3	ACM Journal of Experimental Algorithmics
2	Journal of Statistical Planning and Inference
1	Information Processing Letters
1	Physics Letters. A
1	Information Sciences
1	International Journal for Numerical Methods in Engineering
1	Journal of the American Statistical Association
1	Journal of the Operational Research Society
1	Networks
1	Parallel Computing
1	Algorithmica
1	Transportation Science
1	Annals of Operations Research
1	Journal of Intelligent & Robotic Systems
1	SIAM Journal on Optimization
1	Computational Optimization and Applications
1	Journal of Mathematical Sciences (New York)
1	INFORMS Journal on Computing
1	The Annals of Applied Statistics
1	Mathematical Programming Computation

all top 5

22	Operations research, mathematical programming (90-XX)
12	Combinatorics (05-XX)
12	Computer science (68-XX)
5	Statistics (62-XX)
1	Numerical analysis (65-XX)
1	Mechanics of deformable solids (74-XX)
1	Fluid mechanics (76-XX)
1	Quantum theory (81-XX)
1	Information and communication theory, circuits (94-XX)