Thumbnail
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

   Open content in new tab
Source: ACM Digital Library