Exact Algorithms for Multilayer Topological Via Minimization.

Loading...
Thumbnail Image

Files

TR_88-88.pdf (826.07 KB)
No. of downloads: 759

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.

Notes

Rights