Solving (large scale) matching problems combinatorially

DOI10.1007/BF01594929zbMath0713.90090OpenAlexW1986940512MaRDI QIDQ750322

A. Metz, Ulrich Derigs

Publication date: 1991

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01594929

zbMATH Keywords

computational resultsshortest augmenting pathassignment start procedurefast matching algorithmslarge scale matchingsparse subgraphtwo-phase strategy

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Large-scale problems in mathematical programming (90C06) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

An efficient matching algorithm applied in statistical physics, Ground states of two-dimensional Ising spin glasses: fast algorithms, recent developments and a ferromagnet-spin glass mixture, On the ground-state threshold in random two-dimensional Ising \(\pm J\) models, Blossom V: A new implementation of a minimum cost perfect matching algorithm, Provably good solutions for the traveling salesman problem, A genetic-based framework for solving (multi-criteria) weighted matching problems., Fast algorithms for the undirected negative cost cycle detection problem

Cites Work

• On the use of optimal fractional matchings for solving the (integer) matching problem
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• Solving matching problems with linear programming
• An in-core/out-of-core method for solving large scale assignment problems
• Solving large-scale matching problems efficiently: A new primal matching approach
• The zero pivot phenomenon in transportation and assignment problems and its computational implications
• Maximum matching and a polyhedron with 0,1-vertices
• Unnamed Item