DocumentCode :
390860
Title :
An efficient parallel algorithm for two-layer planarization in graph drawing
Author :
Zheng Tang ; Rong Long Wang ; Qi Ping Cao
Volume :
3
fYear :
2002
fDate :
28-31 Oct. 2002
Firstpage :
1496
Abstract :
We present a parallel algorithm for the two-layer planarization problem using a gradient ascent learning of Hopfield network. This algorithm which is designed to embed a two-layer graph on a plane, uses the Hopfield network to get a near-maximal planar subgraph, and increases the energy by modifying weights in a gradient ascent direction to help the Hopfield network escape from the state of near-maximal planar subgraph to the state of the maximal planar subgraph. The experimental results show that the proposed algorithm can generate better solutions than the traditional Hopfield network.
Keywords :
Hopfield neural nets; computational complexity; graph theory; learning (artificial intelligence); parallel algorithms; Hopfield neural network; NPcomplete problem; gradient ascent learning; graph drawing; maximal planar subgraph; parallel algorithm; planar subgraph; Algorithm design and analysis; Bipartite graph; Computer science; Electronic mail; Engineering drawings; Joining processes; Minimization; Neural networks; Parallel algorithms; Planarization;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
TENCON '02. Proceedings. 2002 IEEE Region 10 Conference on Computers, Communications, Control and Power Engineering
Print_ISBN :
0-7803-7490-8
Type :
conf
DOI :
10.1109/TENCON.2002.1182612
Filename :
1182612
Link To Document :
بازگشت