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

Rong-Long WANG; Zheng TANG; Qi-Ping CAO

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

Rong-Long WANG, Zheng TANG, Qi-Ping CAO

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.2 pp.497-504

Publication Date: 2002/02/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Neural Networks and Bioengineering

Cite this

Copy

Rong-Long WANG, Zheng TANG, Qi-Ping CAO, "A Near-Optimum Parallel Algorithm for Bipartite Subgraph Problem Using the Hopfield Neural Network Learning" in IEICE TRANSACTIONS on Fundamentals, vol. E85-A, no. 2, pp. 497-504, February 2002, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_2_497/_p

Copy

@ARTICLE{e85-a_2_497,
author={Rong-Long WANG, Zheng TANG, Qi-Ping CAO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Near-Optimum Parallel Algorithm for Bipartite Subgraph Problem Using the Hopfield Neural Network Learning},
year={2002},
volume={E85-A},
number={2},
pages={497-504},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={February},}

Copy

TY - JOUR
TI - A Near-Optimum Parallel Algorithm for Bipartite Subgraph Problem Using the Hopfield Neural Network Learning
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 497
EP - 504
AU - Rong-Long WANG
AU - Zheng TANG
AU - Qi-Ping CAO
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2002
AB - 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.
ER -