For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2002/02/01
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>>
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.