Hardness and Methods to Solve CLIQUE  

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

出　　处：《Journal of Computer Science & Technology》2001年第4期388-391,共4页计算机科学技术学报（英文版）

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

摘　　要：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.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.

关 键 词：algorithm NP-HARDNESS approximation ratio dynamic  programming COMPLEXITY 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]