Thumbnail

Maximum-weight independent set is as "well" approximated as the unweighted one

Demange, Marc; Paschos, Vangelis (1999), Maximum-weight independent set is as "well" approximated as the unweighted one. https://basepub.dauphine.fr/handle/123456789/4759

View/Open
Type
Document de travail / Working paper
Date
1999
Publisher
Université Paris-Dauphine
Series title
Cahiers du LAMSADE
Series number
163
Published in
Paris
Metadata
Show full item record
Author(s)
Demange, Marc
Paschos, Vangelis
Subjects / Keywords
l-colorable induced subgraph; chromatic sum; independant set; hereditary problem; NP-completeness; polynomial-time approximation algorithm; computational complexity; combinatorial problems; somme chromatique; graphe induit l-colorable; clique; stable; problème héréditaire; NP-complétude; algorithme polynomial d'approximation; complexité; problèmes combinatoires