Physical Sciences and Mathematics Commons^™

Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

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 …