New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs

Mingyu Xiao

We present an $O^{\ast }(1.0919^n)$-time algorithm for finding a maximum independent set in an $n$-vertex graph with degree bounded by 3, which improves the previously known algorithm of…