A new deterministic annealing algorithm for maximum clique
Arun Jagota, M. Pelilo, Anand Rangarajan · 2000
We propose a new heuristic for approximating the maximum clique problem based on a recently introduced deterministic annealing algorithm which generalizes Waugh and Westewelt's cluster-competitive net. The approach is centered around a fundamental result proved by Motzkin and Straus in the mid-1960s, and recently expanded in various ways, which allows us to formulate the maximum clique problem in terms of a linearly constrained quadratic program. Preliminary experiments on random as well as standard benchmark graphs are presented which demonstrate the validity of the approach.