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 a Graph Layout Problem
Rong-Long WANG Xin-Shun XU Zheng TANG
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2004/02/01
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>>
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.