COMPARISONS OF ENERGY-DESCENT OPTIMIZATION ALGORITHMS FOR MAXIMUM CLIQUE PROBLEMS

A clique of a graph G(V; E) is a subset of V such that every pair of v ertices is connected by an edge in E. Finding a maximum clique of an a rbitrary graph is a well-known NP-complete problem. Recently, several polynomial time ''energy-descent optimization'' algorithms have been p roposed for approximating the maximum clique problem, where they seek a solution by minimizing the energy function representing the constrai nts and the goal Function. In this paper, we propose the binary neural network as an efficient synchronous energy-descent optimization algor ithm. Through two types of random graphs, we compare the performance o f four promising energy-descent optimization algorithms. The simulatio n results show that ''RaCLIQUE,'' the modified Boltzmann machine algor ithm, is the best asynchronous algorithm for random graphs, while the binary neural network is the best one for k random cliques graphs.