A Simple Algorithm for Finding a Maximum Clique and Its Worst‐Case Time Complexity
Miklo Shindo, Etsuji Tomita · Systems and Computers in Japan · 1990
Abstract This paper proposes a new algorithm MAXCLIQUE which finds a maximum clique in an undirected graph with n vertices, and shows that its worst‐case time complexity is O(2n/2.863). For the dual problem of finding a maximum independent set of vertices, Tarjan et al. already have proposed an algorithm of worst‐case time complexity O(2n/3) [2]. However, by comparison, our algorithm is remarkably simpler, and it was confirmed that it runs faster when two algorithms were used for several random graphs and their average running times were measured.