### Greeding matching algorithms, an experimental studyGreeding matching algorithms, an experimental study

Access Restriction
Subscribed

 Author Magun, Jakob Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1998 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Abstract We conduct an experimental study of several greedy algorithms for finding large matchings in graphs. Further we propose a new graph reduction, called $\textit{k}-Block$ Reduction, and present two novel algorithms using extra heuristics in the matching step and $\textit{k}-Block$ Reduction for $\textit{k}$ = 3. Greedy matching algorithms can be used for finding a good approximation of the maximum matching in a graph $\textit{G}$ if no exact solution is required, or as a fast preprocessing step to some other matching algorithm. The studied greedy algorithms run in $\textit{O(m)}.$ 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 $\textit{Gn,p}$ 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. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1998-09-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 3

#### Open content in new tab

Source: ACM Digital Library