A new technique for optimization problems in graph theory
Journal
IEEE Transactions on Computers
Journal Volume
47
Journal Issue
2
Pages
190-196
Date Issued
1998
Author(s)
Yuan, S.-Y.
Abstract
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.
SDGs
Type
journal article