Title :
An Unconstrained Topological Via Minimization Problem for Two-Layer Routing
Author :
Marek-Sadowska, Malagorzata
Author_Institution :
Department of Electrical Engineering and the Computer Sciences and the Electronics Research Laboratory, University of California, Berkeley, CA, USA
fDate :
7/1/1984 12:00:00 AM
Abstract :
Based on graph theory, a study of via minimization problem is presented. We show that the simplest problem of this type is NP-complete and propose a heuristic algorithm for topological via minimization.
Keywords :
Circuits; Graph theory; Heuristic algorithms; Minimization methods; Polynomials; Routing; Tellurium; Topology; Wires;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.1984.1270074
