Hardness and Methods to Solve CLIQUE

作     者：朱大铭 栾峻峰 马绍汉 

作者机构：Department of Computer Science Shandong University Jinan P.R. China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2001年第16卷第4期

页      面：388-391页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：the National Natural Science Foundation of China (Nos.69873027  60073042) 

主　　题：algorithm NP-hardness approximation ratio dynamic programming complexity 

摘      要：The paper briefly reviews NP-hard optimization problems and their inapproximability. The hardness of solving CLIQUE problem is specifically dis- cussed. 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.