Paper Info
Title
A tight analysis of the maximal matching heuristic
Abstract
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.
Year
DOI
Venue
2005
10.1007/11533719_71
COCOON
Field
DocType
Volume
Graph,Discrete mathematics,Combinatorics,Heuristic,Matching (graph theory),Vertex cover,Mathematics,Dense graph
Conference
3595
ISSN
ISBN
Citations 
0302-9743
3-540-28061-8
11
PageRank 
References 
Authors
0.80
10
5
Name
Order
Citations
PageRank
Jean Cardinal133547.57
martine labbe21238108.61
Stefan Langerman3831101.66
Eythan Levy4352.47
Hadrien Melot59514.02