Document Type

Conference Proceeding

Publication Date


Publication Title

Proceedings of the 2nd Annual Israel Symposium on Theory of Computing and Systems



Publisher Name

IEEE Computer Society


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.


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,

Creative Commons License

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