A global optimization approach for solving the maximum clique problem
Pãnos M. Pardalos, A. T. Phillips · International Journal of Computer Mathematics · 1990
The problem of finding a maximum clique of an undirected graph is formulated and solved as a linearly constrained indefinite quadratic global optimization problem. Theoretical upper and lower bounds on the size k of the maximum clique are derived from the global optimization formulation, and a relationship between the set of distinct global maxima of the optimization problem and the set of distinct maximum cliques of the graph is discussed. In addition, some preliminary computational results are also presented.