![](https://d3ilqtpdwi981i.cloudfront.net/xgR-YW2DRme9OPQtzkXk_I0o7OE=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/f3/1b/45/f31b4560-76f9-49c8-84c0-00158de4bbd4/thumbnail_3252fd5d-3b7b-4bcc-a895-11c7c0f1d563.jpg)
The paper provides an efficient method to find all feasible offsets for a given separation in a VLSI channel routing problem in one layer. The prior 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), one can solve the problem 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 are obtained when there are no two-sided nets or all single-sided nets are on one side to the channel. The authors also give improvements upon the naive approach for c≠O(n), including an algorithm with running time independent of c.
© 1993, IEEE.
Available at: http://works.bepress.com/ronald-greenberg/32/
Author Posting. © IEEE, 1993. This is the author's version of the work. It is posted here by permission of {Publisher} for personal use, not for redistribution. The definitive version was published inProceedings of the 2nd Annual Israel Symposium on Theory of Computing and Systems, pages 193--201, http://dx.doi.org/10.1109/ISTCS.1993.253470.
A revised version can be found at http://ecommons.luc.edu/cs_facpubs/84