Greedy Matching Algorithms, an Experimental Study.
Jakob Magun · 1997
We conduct an experimental study of several greedy-type algorithms for finding large matchings in graphs. Further we propose a new graph reduction, called k-Block Reduction, and present two novel algorithms using extra heuristics in the matching step and k-Block Reduction for k = 3. Greedy type matching algorithms can be used for finding a good approximation of the maximum matching in a graph G if no exact solution is required, or as a fast preprocessing step to some other matching algorithm. The studied greedy-type algorithms run in O(m) and are easy to implement and to prove. Our experiments show that a good greedy-type algorithm looses on average at most one edge on random graphs with up to 10,000 vertices. Furthermore the experiments show for which edge densities the maximum matching problem is difficult to solve. 1. Introduction Let G = (V; E) be a graph with vertex set V and edge set E and let n = jV j and m = jEj. A matching is a subset M of the edge set E such that no two ed...