Blossom V: A new implementation of a minimum cost perfect matching algorithm

DOI10.1007/s12532-009-0002-8zbMath1171.05429OpenAlexW2164424155MaRDI QIDQ734352

Vladimir Kolmogorov

Publication date: 20 October 2009

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-009-0002-8

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Algorithms in computer science (68W99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (35)

Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem ⋮ Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs ⋮ Revisiting a cutting-plane method for perfect matchings ⋮ Fault-tolerant quantum error correction for non-abelian anyons ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ Districting for Arc Routing ⋮ On vertex independence number of uniform hypergraphs ⋮ Data Reduction for Maximum Matching on Real-World Graphs ⋮ On matchings, T‐joins, and arc routing in road networks ⋮ Optimal Sokoban solving using pattern databases with specific domain knowledge ⋮ A Branch-and-Price Algorithm for Solving the Hamiltonian p-Median Problem ⋮ Improving a constructive heuristic for the general routing problem ⋮ Learning time-dependent noise to reduce logical errors: real time error rate estimation in quantum error correction ⋮ Partitioning planar graphs: a fast combinatorial approach for max-cut ⋮ A probability metrics approach for reducing the bias of optimality gap estimators in two-stage stochastic linear programming ⋮ A detailed introduction to a minimum-cost perfect matching algorithm based on linear programming ⋮ Approximating the metric TSP in linear time ⋮ The role of entropy in topological quantum error correction ⋮ On optimal flip-flop grouping for VLSI power minimization ⋮ Surface code quantum computing by lattice surgery ⋮ Fast decoders for qudit topological codes ⋮ Topological quantum error correction in the Kitaev honeycomb model ⋮ Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments ⋮ Capacitated arc routing problem with deadheading demands ⋮ Using well-solvable minimum cost exact covering for VLSI clock energy minimization ⋮ OAR lib: an open source arc routing library ⋮ Logical error rate scaling of the toric code ⋮ A magic state’s fidelity can be superior to the operations that created it ⋮ Blossom V ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Computing in combinatorial optimization ⋮ Clustering analysis of a dissimilarity: a review of algebraic and geometric representation ⋮ Easy and difficult exact covering problems arising in VLSI power reduction by clock gating ⋮ A Hybrid Approach to Fast Indirect Quadrilateral Mesh Generation ⋮ Fast algorithms for the undirected negative cost cycle detection problem

Uses Software

• LEDA
• TSPLIB
• VLSI
• Blossom IV
• Triangle
• DIMACS

Cites Work

• Solving (large scale) matching problems combinatorially
• On the use of optimal fractional matchings for solving the (integer) matching problem
• The pairing heap: A new form of self-adjusting heap
• An analysis of alternative strategies for implementing matching algorithms
• An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
• Recursive Star-Tree Parallel Data Structure
• Computing Minimum-Weight Perfect Matchings
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Blossom V: A new implementation of a minimum cost perfect matching algorithm