Document Type

Article

Publication Date

1995

Publication Title

SIAM Journal on Discrete Mathematics

Volume

8

Issue

4

Pages

543-554

Publisher Name

SIAM

Abstract

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.

Identifier

1095-7146

Comments

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).

Creative Commons License

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

Download

Share

COinS