NEURAL NETWORK MODELS FOR THE MAXIMUM CLIQUE PROBLEM

Abstract

In this paper we describe two neural network based algorithms for the Maximum Clique Problem. The developed algorithms provide discrete and continuos descent dynamics respectively to approximate the solution of the quadratic 0-1 formulation of the Maximum Clique Problem. The discrete approach performed better, maintaining computational competitiveness to greedy randomized search procedures. Experimental results on test graphs of size up to 3361 vertices and 5506380 edges are presented