This paper provides an efficient method to find all feasible offsets for a given separation in a very large-scale integration (VLSI) channel-routing problem in one layer. The previous literature considers this task only for problems with no single-sided nets. When single-sided nets are included, the worst-case solution time increases from $\Theta ( n )$ to $\Omega ( n^2 )$, where n is the number of nets. But if the number of columns c is $O( n )$, the problem can be solved in time $O( n^{1.5} \lg n )$, which improves upon a “naive” $O( cn )$ approach. As a corollary of this result, the same time bound suffices to find the optimal offset (the one that minimizes separation). Better running times result when there are no two-sided nets or all single-sided nets are on one side of the channel. This paper also gives improvements upon the naive approach for $c \ne O( n )$, including an algorithm with running time independent of c. An interesting algorithmic aspect of the paper is a connection to discrete convolution.
© Society for Industrial and Applied Mathematics, 1995.
Author Posting. © Society for Industrial and Applied Mathematics, 1995. This article is posted here by permission of the Society for Industrial and Applied Mathematics for personal use, not for redistribution. The article was published in SIAM Journal on Discrete Mathematics, Volume 8, Issue 4, 1995, http://dx.doi.org/10.1137/S0895480193251866
This is a revised version of the conference paper that can be found at http://ecommons.luc.edu/cs_facpubs/114 (along with presentation slides).