A Near-Optimum Parallel Planarization Algorithm
- 15 September 1989
- journal article
- other
- Published by American Association for the Advancement of Science (AAAS) in Science
- Vol. 245 (4923) , 1221-1223
- https://doi.org/10.1126/science.245.4923.1221
Abstract
A near-optimum parallel planarization algorithm is presented. The planarization algorithm, which is designed to embed a graph on a plane, uses a large number of simple processing elements called neurons. The proposed system, composed of an N x N neural network array (where N is the number of vertices), not only generates a near-maximal planar subgraph from a nonplanar graph or a planar graph but also embeds the subgraph on a single plane within 0(1) time. The algorithm can be used in multiple-layer problems such as designing printed circuit boards and routing very-large-scale integration circuits.Keywords
This publication has 2 references indexed in Scilit:
- O(n/sup 2/) algorithms for graph planarizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989
- “Neural” computation of decisions in optimization problemsBiological Cybernetics, 1985