Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537^n)

Van Rooij, Johan; Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis

Van Rooij, Johan; Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010), Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537^n), in Kratochvil, Jan; Li, Angsheng; Fiala, Jiri; Kolman, Petr, Theory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings, Springer : Berlin, p. 373-384

Type

Communication / Conférence

Date

2010

Conference title

7th Annual Conference on Theory and Applications of Models of Computation

Conference date

2010-06

Conference city

Prague

Conference country

République tchèque

Book title

Theory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings

Book author

Kratochvil, Jan; Li, Angsheng; Fiala, Jiri; Kolman, Petr

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

6108/2010

Published in

Berlin

ISBN

978-3-642-13561-3

Pages

373-384

Abstract (EN)

We show that Maximum Independent Set on connected graphs of average degree at most three can be solved in ${\mathcal O}(1.08537^n)$ time and linear space. This improves previous results on graphs of maximum degree three, as our connectivity requirement only functions to ensure that each connected component has average degree at most three. We link this result to exact algorithms of Maximum Independent Set on general graphs. Also, we obtain a faster parameterised algorithm for Vertex Cover restricted to graphs of maximum degree three running in time ${\mathcal O}^*(1.1781^k)$.

Subjects / Keywords

graphs of maximum degree three; Maximum Independent Set