Hardness and Methods to Solve CLIQUE

ZHU Daming, LUAN Junfeng, MA Shaohan. Hardness and Methods to Solve CLIQUE[J]. Journal of Computer Science and Technology, 2001, 16(4).

Citation:

ZHU Daming, LUAN Junfeng, MA Shaohan. Hardness and Methods to Solve CLIQUE[J]. Journal of Computer Science and Technology, 2001, 16(4).

Citation:

ZHU Daming, LUAN Junfeng, MA Shaohan. Hardness and Methods to Solve CLIQUE[J]. Journal of Computer Science and Technology, 2001, 16(4).

Abstract

The paper briefly reviews NP-hard optimization problems and theirinapproximability. The hardness of solving CLIQUE problem isspecifically discussed. A dynamic-programming algorithm and its improvedversion for CLIQUE are reviewed and some additional analysis ispresented. The analysis implies that the improved algorithm, HEWN(hierarchical edge-weighted network),only provides a heuristic or useful method, but cannot be called apolynomial algorithm.

FullText(HTML)

Export File