DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
Rechercher
(titres de publication, de périodique et noms de colloque inclus)
2005-09-07 - Article/Dans un journal avec peer-review - Anglais - 9 page(s)

Cardinal J., Labbé M., Langerman S., Levy E., Mélot Hadrien , "A tight analysis of the maximal matching heuristic" in Lecture Notes in Computer Science, 3595, 701-709

  • Edition : Springer, Berlin (Germany)
  • Codes CREF : Théorie des graphes (DI1146), Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Algorithmique (S825)
Texte intégral :

Abstract(s) :

(Anglais) 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 min{2,1/(1-1-?)} for graphs with an average degree at least en and to min{2,1/?} for graphs with a minimum degree at least en.

Identifiants :
  • ISSN : 0302-9743
  • DOI : 10.1007/11533719_71
  • ISBN : 3-540-28061-8