TY - JOUR T1 - Parallel Algorithms for Channel Routing in the Knock-Knee Model JF - SIAM Journal on Computing Y1 - 1991 A1 - JaJa, Joseph F. A1 - Chang,Shing-Chong KW - channel routing KW - Layout KW - left-edge algorithm KW - line packing KW - Parallel algorithms KW - VLSI design AB - The channel routing problem of a set of two-terminal nets in the knock-knee model is considered. A new approach to route all the nets within $d$ tracks, where $d$ is the density, such that the corresponding layout can be realized with three layers is developed. The routing and the layer assignment algorithms run in $O(\log n)$ time with $n / \log n$ processors on the CREW PRAM model under the reasonable assumption that all terminals lie in the range $[1,N]$, where $N = O(n)$. VL - 20 UR - http://link.aip.org/link/?SMJ/20/228/1 CP - 2 M3 - 10.1137/0220014 ER -