A Near-Optimum Parallel Algorithm for Bipartite Subgraph Problem Using the Hopfield Neural Network Learning

Rong-Long WANG  Zheng TANG  Qi-Ping CAO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.2   pp.497-504
Publication Date: 2002/02/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Neural Networks and Bioengineering
bipartite subgraph problem,  maximum cut problem,  Hopfield neural network,  gradient ascent learning,  NP-complete problem,  

Full Text: PDF>>
Buy this Article

A near-optimum parallel algorithm for bipartite subgraph problem using gradient ascent learning algorithm of the Hopfield neural networks is presented. This parallel algorithm, uses the Hopfield neural network updating to get a near-maximum bipartite subgraph and then performs gradient ascent learning on the Hopfield network to help the network escape from the state of the near-maximum bipartite subgraph until the state of the maximum bipartite subgraph or better one is obtained. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that our algorithm finds the solution quality is superior to that of best existing parallel algorithm. We also test the proposed algorithm on maximum cut problem. The simulation results also show the effectiveness of this algorithm.