%0 Journal Article
%T Hardness and Methods to Solve CLIQUE
%A Zhu Daming
%A LUAN Junfeng
%A MA Shaohan
%A <br>朱大铭
%A 栾峰峰
%J 计算机科学技术学报
%D 2001
%I 
%X 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.
%K algorithm
%K NP-hardness
%K approximation ratio
%K dynamic
%K programming
%K complexity<br>程序设计
%K 算法
%K CLIQUE
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=119526CA94D64C568D4A139AAB695D04&yid=14E7EF987E4155E6&vid=7801E6FC5AE9020C&iid=E158A972A605785F&sid=2B25C5E62F83A049&eid=2B25C5E62F83A049&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=14