送交者: starfire 于 2006-2-28, 23:42:02:

回答: Knuth提到的这个中国人是谁？ 由 gentoo 于 2006-2-28, 19:10:03:

朱大铭，栾峻峰，马绍汉，Hardness and methods to solve CLIQUE, 计算机学报英文版，2001年7月。

Hardness and Methods to Solve CLIQUE

ZHU Daming (朱大铭), LUAN Junfeng (栾峻峰) and MA Shaohan (马绍汉)
Department of Computer Science, Shandong University, Jinan 250100, P.R. China
E-mail: zdm@cs.sdu.edu.cn

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.

• http://jcst.ict.ac.cn/cn/qwjs.htm

• 不是这篇 - John (373 bytes) 2006-3-01, 04:29:42
  • 我知道不是那篇，但好像那文章讨论的是别人的算法,指出其不是多项式算法 - starfire (28 bytes) 2006-3-01, 15:10:02
  • I guess, it is a nice piece of work even it contains a bug - test2test (171 bytes) 2006-3-01, 06:34:27
    • It was a nice try, but - John (651 bytes) 2006-3-01, 08:39:30

加跟贴