Algorithms for the maximum clique problem
L. Gibbons, Donald W. Hearn · 1994
The maximum clique problem is an N P-hard discrete combinatorial problem. As such, heuristic procedures for an approximate solution are the only recourse on large dense problem instances. In this dissertation, the maximum clique problem is studied, and algorithms for its solution are developed. This study can be divided into two main parts. First, the maximum clique problem is formulated as a continuous indefinite quadratic program. The global solutions of this program are studied, and the insight gained from this study is used in the subsequent development of a heuristic. The heuristic is deterministic and requires no parameter calibration. Second, an exact algorithm for the maximum clique problem based on partial enumeration is developed. Computational results on the DIMACS benchmark library are provided. These results provide evidence that both the heuristic and the exact algorithm perform extremely well.