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   Vol.E84-A   No.7   pp.1799-1802
Publication Date: 2001/07/01
Online ISSN: 
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>>
Buy this Article

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.