OPTIMAL-ALGORITHMS ON THE PIPELINED HYPERCUBE AND RELATED NETWORKS

We present parallel algorithms for several important combinatorial pro blems such as the all nearest smaller values problem, triangulating a monotone polygon, and line packing. These algorithms achieve linear sp eedups on the pipelined hypercube, and provably optimal speedups on th e shuffle-exchange and the cube-connected-cycles, for any number p of processors satisfying 1 less-than-or-equal-to p less-than-or-equal-to n/((log3 n)(10 log n)2), where n is the input size. The lower bound re sults are established under no restriction on how the input is mapped into the local memories of the different processors.