Minimum Vertex Cover Problem Optimization Using Hopfield Neural Network: Graph Theory Problem Optimization
This paper presents the implementation of efficient techniques to map the minimum vertex cover onto the Hopfield neural networks. Neural networks are a new method of programming computers. They are exceptionally good at performing pattern recognition and other tasks that are very difficult to program using conventional techniques. Programs that employ neural nets are also capable of learning on their own and adapting to changing conditions. For given graph G= (V, E), minimum vertex cover is the problem to find the smallest subset of S V such that each edge contains at least one vertex of S. This approach can be used to find near-optimum solutions for these problems in parallel, and particularly the network algorithm always yields minimum vertex covers. A systematic way of deriving energy functions is implemented. Based on this relationship, 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 algorithms for vertex cover problems.
Experimental results show that the performance of this method is better than that of the well-known sequential greedy algorithm and, due to the inherent properties of Hopfield neural networks. This algorithm is suitable for massively parallel execution. Large-scale neural networks may become a significant advantage for the application area like scheduling, information retrieval, and fault detection etc...
Keywords: Optimization in Neural Network, Minimum vertex cover problem, Hopfield Model, Mapping of Minimum Vertex Cover onto Hopfiled Network.
Prof. Pravinkumar Kamde
Assistant Professor, Computer Engg Department, Sinhgad College of Engg.
Prof. P. J. Kulkarni
Walchand College of Engineering