Finding a Maximum Independent Set

Authors: Robert Endre Tarjan, Anthony E. Trojanowski - SIAM Journal on Computing 1977 cited by 474

We present an algorithm which finds a maximum independent set in an n-vertex graph in $O(2^{n/3})$ time. The algorithm can thus handle graphs roughly three times as large as could be analyzed using a naive algorithm.