Using genetic algorithms for planarization problems
F. Comellas
Departament de Matemàtica Aplicada i Telemàtica;
Universitat Politècnica de Catalunya
Computational and Applied Mathematics, I, C. Brezinski and
U. Kulish (Eds.), Elsevier Science Publishers B.V. (North Holland),
pp. 93-100, (1992). ISBN 0-444-89701-1
Two near-optimum planarization algorithms are presented.
The algorithms belong to a general class of algorithms known
as genetic algorithms because the search procedures on which
they are based are inspired by the mechanics of natural selection
and natural genetics.
The first algorithm is intended to generate a near-maximal
planar subgraph from a given graph and also provides the
routing information needed to embed the subgraph on the plane.
The second planarization algorithm studied finds a near-maximum
independent set of a circle graph. This algorithm may be used for
finding a routing on one layer from a set of n two-pin nets
in a channel. After small modifications, it may also be used
to predict the
secondary structure of ribonucleic acids.
The main advantage of both algorithms
is that they are easily implemented in a parallel computer.
Load:
