An improved exact algorithm for maximum independent set in sparse graphs
Nicolas Bourgeois, Bruno Escoffier, Vangélis Th. Paschos · HAL (Le Centre pour la Communication Scientifique Directe) · 2008
We present an O* (1.0977n) tree-search 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.