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 -