Solving The Maximum Clique Problem Using Saturated Dynamic Neural Networks

The maximum clique problem (MCP) is a classical graph-theoretic problem, which aims to find the maximum complete subgraph of a given graph G. Ever since the MCP was proposed, it has been investigated intensively and applied to many domains including pattern recognition, cluster analysis, graph coloring, VLSI circuit design, etc.. As the MCP is NP-hard, an appropriate approach to treating this problem is to design various heuristic algorithms. One of the feasible solutions is to use the neural network based algorithms. In 1999, Pekergin et al. proposed a neural network based algorithm for the MCP (which is known as the saturated linear dynamic network algorithm or briefly the SLDN algorithm). Inspired by this algorithm, in this thesis we develop a new algorithm for the MCP, which incorporates nonlinear self-feedback into the SLDN algorithm.The main work in this thesis includes the following.1. Review the basic concepts, background and the state of the art of the maximum clique problems as well as the neural networks. Illustrate the history and some interesting results of solving the MCP using neural networks.2. Expatiate the saturated linear dynamic network algorithm, point out that the SLDN algorithm utilizes gradient descent type optimization technique. Consequently, it might converge to a local minimum. This is the limitation of the SLDN algorithm when applied to solve the MCP.3. Propose a novel neural network based algorithm for the MCP. This algorithm incorporates nonlinear self-feedback into the SLDN algorithm. Simulation results show that to a certain extent, the proposed algorithm can prevent the proposed neural network from falling into local optimal point, and its performance is statistically superior to the SLDN algorithm.