%0 Journal Article
%J SIAM Journal on Computing
%D 1991
%T Parallel Algorithms for Channel Routing in the Knock-Knee Model
%A JaJa, Joseph F.
%A Chang,Shing-Chong
%K channel routing
%K Layout
%K left-edge algorithm
%K line packing
%K Parallel algorithms
%K VLSI design
%X 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)$.
%B SIAM Journal on Computing
%V 20
%P 228 - 245
%8 1991///
%G eng
%U http://link.aip.org/link/?SMJ/20/228/1
%N 2
%R 10.1137/0220014