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

Thumbnail
Date
2008
Collection title
Lecture Notes in Computer Science
Collection Id
5018
Link to item file
http://hal.archives-ouvertes.fr/hal-00203163/en/
Dewey
Recherche opérationnelle
Sujet
graphs; max independent set
DOI
http://dx.doi.org/10.1007/978-3-540-79723-4_7
Conference name
Third International Workshop on Parameterized and Exact Computation Parameterized and Exact Computation (IWPEC 2008)
Conference date
05-2008
Conference city
Victoria
Conference country
Canada
Book title
Parameterized and Exact Computation Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008, Proceedings
Author
Grohe, Martin; Niedermeier, Rolf
Publisher
Springer
Publisher city
Berlin
Year
2008
Pages number
227
ISBN
978-3-540-79722-7
Book URL
http://dx.doi.org/10.1007/978-3-540-79723-4
URI
https://basepub.dauphine.fr/handle/123456789/6008
Collections
Metadata
Show full item record
Author
Bourgeois, Nicolas
Escoffier, Bruno
Paschos, Vangelis
Type
Communication / Conférence
Item number of pages
55-65
Abstract (EN)
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.