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 Hopfield Network Learning Algorithm for Graph Planarization
Zheng TANG Rong Long WANG Qi Ping CAO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/07/01
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Neural Networks and Bioengineering
graph planarization, Hopfield neural network, gradient ascent learning, NP-complete problem,
Full Text: PDF>>
A gradient ascent learning algorithm of the Hopfield neural networks for graph planarization is presented. This learning algorithm uses the Hopfield neural network to get a near-maximal planar subgraph, and increases the energy by modifying parameters in a gradient ascent direction to help the network escape from the state of the near-maximal planar subgraph to the state of the maximal planar subgraph or better one. The proposed algorithm is applied to several graphs up to 150 vertices and 1064 edges. The performance of our algorithm is compared with that of Takefuji/Lee's method. Simulation results show that the proposed algorithm is much better than Takefuji/Lee's method in terms of the solution quality for every tested graph.