Greeding matching algorithms, an experimental study

We conduct an experimental study of several greedy algorithms for finding large matchings in graphs. Further we propose a new graph reduction, called <i>k</i>-Block Reduction, and present two novel algorithms using extra heuristics in the matching step and <i>k</i>-Block Reduction for <i>k</i> = 3. Greedy matching algorithms can be used for finding a good approximation of the maximum matching in a graph <i>G</i> if no exact solution is required, or as a fast preprocessing step to some other matching algorithm. The studied greedy algorithms run in <i>O(m)</i>. They are easy to implement and their correctness and their running time are simple to prove. Our experiments show that a good greedy algorithm looses on average at most one edge on random graphs from <i>G<inf>n,p</inf></i> with up to 10,000 vertices. Furthermore the experiments show for which edge densities in random graphs the maximum matching problem is difficult to solve.