Report Number: CS-TR-76-550
Institution: Stanford University, Department of Computer Science
Title: Finding a maximum independent set
Author: Tarjan, Robert Endre
Author: Trojanowski, Anthony E.
Date: June 1976
Abstract: We present an algorithm which finds a maximum independent set in an n-vertex graph in 0($2^{n/3}$) time. The algorithm can thus handle graphs roughly three times as large as could be analyzed using a naive algorithm.
http://i.stanford.edu/pub/cstr/reports/cs/tr/76/550/CS-TR-76-550.pdf