Systems and Computers in Japan · 1990 · 32 citations · 3 references
ComputingComputer ScienceAlgorithmsCombinatoricsComputational GeometryAlgorithm AnalysisAlgorithmic ComplexityComputational ComplexityGraph AlgorithmsGraph TheoryTime ComplexityClique AlgorithmsCliquesComputational Complexity Of Graph AlgorithmsIndependent Set AlgorithmsRandom GraphsRandomized Graph AlgorithmsSimple AlgorithmWorst-case Complexity
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.
3
Algorithm 457: finding all cliques of an undirected graph
Coen Bron, Joep Kerbosch · Communications of the ACM · 1973 · 2.5K citations · Full text
Finding a Maximum Independent Set
Robert E. Tarjan, Anthony E. Trojanowski · SIAM Journal on Computing · 1977 · 474 citations
Finding a Maximum Clique in an Arbitrary Graph
Egon Balas, Chang Sung Yu · SIAM Journal on Computing · 1986 · 293 citations