An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs

Thumbnail
Date
2008
Titre de la collection
Lecture Notes in Computer Science
n° dans la collection
5018
Lien vers un document non conservé dans cette base
http://hal.archives-ouvertes.fr/hal-00203163/en/
Indexation documentaire
Recherche opérationnelle
Subject
graphs; max independent set
Réf version publiée
http://dx.doi.org/10.1007/978-3-540-79723-4_7
Titre du colloque
Third International Workshop on Parameterized and Exact Computation Parameterized and Exact Computation (IWPEC 2008)
Date du colloque
05-2008
Ville du colloque
Victoria
Pays du colloque
Canada
Titre de l'ouvrage
Parameterized and Exact Computation Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008, Proceedings
Auteur
Grohe, Martin; Niedermeier, Rolf
Nom de l'éditeur
Springer
Ville de l'éditeur
Berlin
Année
2008
Nombre total de pages
227
ISBN
978-3-540-79722-7
URL de l'ouvrage
http://dx.doi.org/10.1007/978-3-540-79723-4
URI
https://basepub.dauphine.fr/handle/123456789/6008
Collections
Métadonnées
Afficher la notice complète
Auteur
Bourgeois, Nicolas
Escoffier, Bruno
Paschos, Vangelis
Type
Communication / Conférence
Nombre de pages du document
55-65
Résumé en anglais
We present an O *(1.0977 n ) search-tree based exact algorithm for max independent set in graphs with maximum degree 3. It can be easily seen that this algorithm also works in graphs with average degree 3.