Algorithms for maximum independent sets

Abstract

An algorithm is presented which finds (the size of) a maximum independent set of an n vertex graph in time O(2^0.276n) improving on a previous bound of $\text{O(2}{}^{\mathrm{<mtext>n</mtext><mtext>3</mtext>}}\text{)}$. The improvement comes principally from three sources: first, a modified recursive algorithm based on a more detailed study of the possible subgraphs around a chosen vertex; second, an improvement, not in the algorithm but in the time bound proved, by an argument about connected regular graphs; third, a time-space trade-off which can speed up recursive algorithms from a fairly wide class.