# Top-Bottom Routing around a Rectangle is as Easy as Computing Prefix Minima

Title | Top-Bottom Routing around a Rectangle is as Easy as Computing Prefix Minima |

Publication Type | Journal Articles |

Year of Publication | 1994 |

Authors | Berkman O, JaJa JF, Krishnamurthy S, Thurimella R, Vishkin U |

Journal | SIAM Journal on Computing |

Volume | 23 |

Issue | 3 |

Pagination | 449 - 465 |

Date Published | 1994/// |

Keywords | Parallel algorithms, pram algorithms, prefix minima, VLSI routing |

Abstract | A new parallel algorithm for the prefix minima problem is presented for inputs drawn from the range of integers $[1..s]$. For an input of size $n$, it runs in $O(\log \log \log s)$ time and $O(n)$ work (which is optimal). A faster algorithm is presented for the special case $s = n$; it runs in $O(\log ^ * n)$ time with optimal work. Both algorithms are for the Priority concurrent-read concurrent-write parallel random access machine (CROW PRAM). A possibly surprising outcome of this work is that, whenever the range of the input is restricted, the prefix minima problem can be solved significantly faster than the $\Omega (\log \log n)$ time lower bound in a decision model of parallel computation, as described by Valiant [SIAM J. Comput., 4 (1975), pp. 348–355].The top-bottom routing problem, which is an important subproblem of routing wires around a rectangle in two layers, is also considered. It is established that, for parallel (and hence for serial) computation, the problem of top-bottom routing is no harder than the prefix minima problem with $s = n$, thus giving an $O(\log ^ * n)$ time optimal parallel algorithm for the top-bottom routing problem. This is one of the first nontrivial problems to be given an optimal parallel algorithm that runs in sublogarithmic time. |

URL | http://link.aip.org/link/?SMJ/23/449/1 |

DOI | 10.1137/S0097539791218275 |