Clique은 그래프상의 각 노드가 서로 상호연결된 하위그래프를 말한다. 따라서 각 노드에서 하위그래프상의 어떠한 노드로도 바로 갈 수 있게 된다. 이러한 clique을 찾는 문제는 knapsack packing, graph coloring, vertex cover, Hamiltonian path, 3-SAT, 그리고 유명한 TSP와 함께 computer science에서 여전히 풀기어려운 과제로 남아 있는 NP-complete 문제이다. 아무리 하드웨어와 기술이 발달하고 수천개의 프로세서가 있는 슈퍼컴퓨터라도 여전히 천문학적인 시간을 요구하는 이러한 문제는 알고리즘의 중요성을 실감하게 한다.

내용보기 : http://www.ibluemojo.com/school/clique_algorithm.html