@article {15006, title = {Parallel Algorithms for Channel Routing in the Knock-Knee Model}, journal = {SIAM Journal on Computing}, volume = {20}, year = {1991}, month = {1991///}, pages = {228 - 245}, abstract = {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)$.}, keywords = {channel routing, Layout, left-edge algorithm, line packing, Parallel algorithms, VLSI design}, doi = {10.1137/0220014}, url = {http://link.aip.org/link/?SMJ/20/228/1}, author = {JaJa, Joseph F. and Chang,Shing-Chong} }