Document Type


Publication Date


Publication Title

SIAM Journal on Discrete Mathematics






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.


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,

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.