A saturated linear dynamical network for approximating maximum clique

We use a saturated linear gradient dynamical network for finding an approxi mate solution to the maximum clique problem. We show that for almost all in itial conditions, any solution of the network defined on a closed hypercube reaches one of the vertices of the hypercube, and any such vertex correspo nds to a maximal clique. We examine the performance of the method on a set of random graphs and compare the results with those of some existing method s. The proposed model presents a simple continuous, yet powerful, solution in approximating maximum clique, which may outperform many relatively compl ex methods, e.g,, Hopfield-type neural network based methods and convention al heuristics.