A Simple Algorithm for Finding a Maximum Clique and Its Worst‐Case Time Complexity
- 1 January 1990
- journal article
- research article
- Published by Wiley in Systems and Computers in Japan
- Vol. 21 (3) , 1-13
- https://doi.org/10.1002/scj.4690210301
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.Keywords
This publication has 3 references indexed in Scilit:
- Finding a Maximum Clique in an Arbitrary GraphSIAM Journal on Computing, 1986
- Finding a Maximum Independent SetSIAM Journal on Computing, 1977
- Algorithm 457: finding all cliques of an undirected graphCommunications of the ACM, 1973