Premium
A new algorithm for general matching problems using network flow subproblems
Author(s) -
Lessard Réjean,
Rousseau JeanMarc,
Minoux Michel
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190406
Subject(s) - polytope , matching (statistics) , flow network , convergence (economics) , flow (mathematics) , algorithm , set (abstract data type) , mathematical optimization , computer science , constraint (computer aided design) , minimum cost flow problem , code (set theory) , mathematics , maximum flow problem , discrete mathematics , statistics , geometry , economics , programming language , economic growth
We describe a new algorithm for minimum cost perfect matching problems in arbitrary (nonbipartite) graphs based on an active constraint set strategy on the whole set of constraints defining the matching polytope (the so‐called Edmonds' constraints or blossom inequalities). At each step, the resulting subproblem reduces to a minium cost network flow problem which may be solved either via classical network flow algorithms, or via primal network flow algorithms. Finite convergence of the algorithm is proved under a nondegeneracy assumption and an anticycling procedure is defined for ensuring finite termination in degenerate cases. Computer experiments using a primal code for the network flow subproblems show that this approach appears to be competitive even with respect to the most efficient general matching codes currently described in the literature.