On computing maximum size matchings in graphs

Abstract

The problem of finding a maximum-size matching in a graph appears in many situations in graph theory. Therefore it is crucial to compute such matchings in a fast way. In some cases a hybrid algorithm, consisting of an heuristic to find a start-matching and an exact algorithm to compute the maximum-size matching, appears to be much faster than classical algorithms. We show a way to implement appropriate heuristics, exact algorithms and hybrid algorithms in C++ and compare their performance on different random graphs. To reduce the programming-effort , we used comprehensible techniques. These techniques can be implemented indepen- dent of programming languages and the operating systems.