Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
A Tight Analysis of the Maximal Matching Heuristic
verfasst von : Jean Cardinal, Martine Labbé, Stefan Langerman, Eythan Levy, Hadrien Mélot
Erschienen in: Computing and Combinatorics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the worst-case performance of the maximal matching heuristic applied to the
Minimum Vertex Cover
and
Minimum Maximal Matching
problems, through a careful analysis of tight examples. We show that the tight worst-case approximation ratio is asymptotic to
${\rm min}\, \{2, 1/(1-\sqrt{1-\epsilon})\}$
for graphs with an average degree at least
εn
and to min {2, 1/
ε
} for graphs with a minimum degree at least
εn
.