An efficient algorithm for the bipartite matching problem

DOI10.1016/0377-2217(86)90218-3MaRDI QIDQ1069866zbMATH OpenOpenAlexFDO

Authors Paolo Carraresi, Claudio Sodini

Publication date 1986

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(86)90218-3

zbMATH Keywords

threshold algorithmminimum cost bipartite matching problemshortest path sub-problems

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35)

Review text

The minimum cost bipartite matching problem is considered. An approach based on the solution of a sequence of shortest path sub-problems is proposed. The particular structure of the problem and the use of reduced costs make it possible to devise an efficient threshold algorithm to solve these sub-problems. The computational behaviour of the proposed procedure is analyzed.

Recommendations

• A new algorithm for general matching problems using network flow subproblems
• Faster scaling algorithms for general graph matching problems
• An 0(n log n) algorithm for the convex bipartite matching problem
• scientific article; zbMATH DE number 91028
• scientific article; zbMATH DE number 515937

Cites work

• A shortest augmenting path method for solving minimal perfect matching problems
• A Successive Shortest Path Algorithm for The Assignment Problem
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• scientific article; zbMATH DE number 3791946 (Why is no real title available?)
• Solving the Assignment Problem by Relaxation
• The alternating basis algorithm for assignment problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(23)

• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• A polynomial algorithm for b-matchings: An alternative approach
• The uniquely solvable bipartite matching problem
• An efficient matching algorithm applied in statistical physics
• Max-min matching problems with multiple assignments
• \(n\)-Tokyoites' loop-line commuter problem
• A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints
• An efficient algorithm for finding a two-pair, and its applications
• A new algorithm for solving a special matching problem with a general form value function under constraints
• An algorithm for computing the matching capacity
• On the computational complexity of the bipartizing matching problem
• Extended Kuhn-Munkres algorithm for constrained matching search
• On bipartite matchings of minimum density
• scientific article; zbMATH DE number 91028 (Why is no real title available?)
• scientific article; zbMATH DE number 123780 (Why is no real title available?)
• scientific article; zbMATH DE number 2040948 (Why is no real title available?)
• An extendable stable matching algorithm of a kind of bipartite graph
• An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem
• A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
• A min-max theorem for the minimum fleet-size problem
• Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching
• An 0(n log n) algorithm for the convex bipartite matching problem
• Nonlinear bipartite matching

This page was built for publication: An efficient algorithm for the bipartite matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1069866)