An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
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érenceExternal document link
http://hal.archives-ouvertes.fr/hal-00203163/en/Date
2008Conference title
Third International Workshop on Parameterized and Exact Computation Parameterized and Exact Computation (IWPEC 2008)Conference date
2008-05Conference city
VictoriaConference country
CanadaBook title
Parameterized and Exact Computation Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008, ProceedingsBook author
Grohe, Martin; Niedermeier, RolfPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
5018Published in
Berlin
ISBN
978-3-540-79722-7
Number of pages
227Pages
55-65
Publication identifier
Metadata
Show full item recordAbstract (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 setRelated items
Showing items related by title and author.
-
van Rooij, Johan; Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2008) Document de travail / Working paper
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis; Van Rooij, Johan (2012) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Van Rooij, Johan; Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence