A new technique for optimization problems in graph theory

This paper presents an efficient technique to map the minimum vertex cover and two closely related problems (maximum independent set and maximum clique) onto the Hopfield neural networks. The proposed approach can be used to find near-optimum solutions for these problems in parallel, and particularly the network algorithm always yields minimal vertex covers. A systematic way of deriving energy functions is described. Based on these relationships, other NP-complete problems in graph theory can also be solved by neural networks. Extensive simulations were performed, and the experimental results show that the network algorithm outperforms the well-known greedy algorithm for vertex cover problems.