|
1. |
Exact algorithms for multilayer topological via minimization
Rim, C.S.; Kashiwabara, T.; Nakajima, K.;
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Volume 8,
Issue 11,
Nov. 1989
Page(s):1165
-
1173
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
|
Cart
