Technical Report 439-1995

Title

Cardinality Matching: Heuristic Search for Augmenting Paths

Authors

Rolf H. Möhring and Matthias Müller-Hannemann

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

Abstract

A new heuristic for the cardinality matching problem is given and compared with different greedy heuristics. A modified depth first search is used to search heuristically for an augmenting path with respect to a given matching. In a large number of test-runs on randomly generated graphs, our heuristic usually gave optimal solutions, and only in rare cases we observed cardinalities one less than the optimal ones. Computational results on sparse graphs which are known to be difficult from the DIMACS challenge on cardinality matching show that this heuristic combined with a starting procedure of Karp and Sipser [KS81] is much faster than many efficient exact algorithms. A proof of optimality was either obtained by a tight upper bound or by running one phase of the algorithm of Micali and Vazirani [MV80].