Title :
Exact algorithms for multilayer topological via minimization
Author :
Rim, Chong S. ; Kashiwabara, Toshinobu ; Nakajima, Kazuo
Author_Institution :
Maryland Univ., College Park, MD, USA
fDate :
11/1/1989 12:00:00 AM
Abstract :
In the past, several heuristic algorithms were developed for the topological via minimization problem. It was very recently shown to be NP-hard even for the two-layer channel routing case with two-terminal nets only. The authors show that if no local net exists in a channel, this problem is solvable in O(kn2) time even for k layers, where n is the number of two-terminal nets. As an extension of this case, they consider the problem for the case of k-layer circular channel routing in which no local net exists and present an O(n2k+1) time algorithm
Keywords :
circuit layout; computational complexity; minimisation; network topology; NP-hard; heuristic algorithms; multilayer circular channel routeing; network topology; topological via minimization problem; two-terminal nets; Conductors; Heuristic algorithms; Minimization methods; Nonhomogeneous media; Polynomials; Routing; Shape; Wire;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
