TOP-BOTTOM ROUTING AROUND A RECTANGLE IS AS EASY AS COMPUTING PREFIX MINIMA

A new parallel algorithm for the prefix minima problem is presented fo r 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 i n O(log n) time with optimal work. Both algorithms are for the Priori ty concurrent-read concurrent-write parallel random access machine (CR CW PRAM). A possibly surprising outcome of this work is that, whenever the range of the input is restricted, the prefix minima problem can b e solved significantly faster than the OMEGA(log log n) time lower bou nd in a decision model of parallel computation, as described by Valian t [SIAM J. Comput., 4 (1975), pp. 348-355]. The top-bottom routing pro blem, which is an important subproblem of routing wires around a recta ngle in two layers, is also considered. It is established that, for pa rallel (and hence for serial) computation, the problem of top-bottom r outing is no harder than the prefix minima problem with s = n, thus gi ving an 0 (log n) time optimal parallel algorithm for the top-bottom routing problem. This is one of the first nontrivial problems to be gi ven an optimal parallel algorithm that runs in sublogarithmic time.