A Simple Algorithm for Finding a Maximum Clique and Its Worst‐Case Time Complexity

Miklo Shindo, Etsuji Tomita

Systems and Computers in Japan · 1990 · 32 citations · 3 references

Concepts

Abstract

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 (2 n/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 (2 n/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.

References

3