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

Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis

Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2008), An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs, in Grohe, Martin; Niedermeier, Rolf, Parameterized and Exact Computation Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008, Proceedings, Springer : Berlin, p. 55-65. http://dx.doi.org/10.1007/978-3-540-79723-4_7

Type

Communication / Conférence

External document link

http://hal.archives-ouvertes.fr/hal-00203163/en/

Date

2008

Conference title

Third International Workshop on Parameterized and Exact Computation Parameterized and Exact Computation (IWPEC 2008)

Conference date

2008-05

Conference city

Victoria

Conference country

Canada

Book title

Parameterized and Exact Computation Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008, Proceedings

Book author

Grohe, Martin; Niedermeier, Rolf

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

5018

Published in

Berlin

ISBN

978-3-540-79722-7

Number of pages

227

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.

Subjects / Keywords

graphs; max independent set