A Near-Optimum Parallel Algorithm for a Graph Layout Problem

Rong-Long WANG  Xin-Shun XU  Zheng TANG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.2   pp.495-501
Publication Date: 2004/02/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Neural Networks and Bioengineering
graph layout,  crossing number,  NP-complete problem,  Hopfield neural network,  learning algorithm,  

Full Text: PDF>>
Buy this Article

We present a learning algorithm of the Hopfield neural network for minimizing edge crossings in linear drawings of nonplanar graphs. The proposed algorithm uses the Hopfield neural network to get a local optimal number of edge crossings, and adjusts the balance between terms of the energy function to make the network escape from the local optimal number of edge crossings. The proposed algorithm is tested on a variety of graphs including some "real word" instances of interconnection networks. The proposed learning algorithm is compared with some existing algorithms. The experimental results indicate that the proposed algorithm yields optimal or near-optimal solutions and outperforms the compared algorithms.