Clique finding relaxation labeling networks
Marcello Pelillo · ARCA (Università Ca' Foscari Venezia) · 1996
The maximum clique problem is a well-known difficult optimization problem which is frequently encountered in computer vision and pattern recognition. In this paper, we show how to approximately solve it by means of a simple relaxation labeling network, of the type originally introduced by Rosenfeld, Hummel, and Zucker. The approach is based on a remarkable result of Motzkin and Straus which allows us to formulate the problem in terms of a certain continuous linearly constrained quadratic optimization problem. Extensive simulations are presented which practically demonstrate the validity of the proposed model.