Date
1992
Indexation documentaire
Recherche opérationnelle
Subject
computational complexity; independent set; combinatorial problems; analysis of algorithms; Approximation algorithms
Nom de la revue
Information Processing Letters
Volume
44
Numéro
1
Date de publication
11-1992
Pages article
11-13
Nom de l'éditeur
Elsevier
Type
Article accepté pour publication ou publié
Résumé en anglais
We show how we can improve the approximation ratio for the independent set problem on a graph. We obtain thus an approximation ratio asymptotically equal to δ/2, in place of δ−1, where δ is the maximum degree of the graph.
