Exact Algorithms for Multilayer Topological Via Minimization.
Exact Algorithms for Multilayer Topological Via Minimization.
Loading...
Publication or External Link
Date
1988
Advisor
Citation
DRUM DOI
Abstract
We consider the topological via minimization problem in which each of n nets has two terminals to be connected and the routing area consists of k layers. We first show that this problem is solvable in O(kn^2) time, using a minimum cost network flow algorithm, for the usual channel routing case in which no local net exists. We then consider the problem for the case of "circular" channel routing in which no local net exists, and present an O(n^(2k+1)) time algorithm using dynamic programming.