Exact Algorithms for Multilayer Topological Via Minimization.

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.