Hardness and methods to solve CLIQUE.

Authors :: Zhu, Daming
Luan, Junfeng
Ma, Shaohan
Source :: Journal of Computer Science & Technology (10009000); Jul2001, Vol. 16 Issue 4, p388-391, 4p
Publication Year :: 2001
Abstract: The paper briefly reviews NP-hard optimization problems and their inapproximability. The hardness of solving CLIQUE problem is specifically discussed. A dynamic-programming algorithm and its improved version for CLIQUE are reviewed and some additional analysis is presented. The analysis implies that the improved algorithm, HEWN (hierarchical edge-weighted network), only provides a heuristic or useful method, but cannot be called a polynomial algorithm. [ABSTRACT FROM AUTHOR]