Optimal algorithms on the pipelined hypercube and related networks
Joseph F. JáJá, Kwan Woo Ryu · IEEE Transactions on Parallel and Distributed Systems · 1993
Parallel algorithms for several important combinatorial problems such as the all nearest smaller values problem, triangulating a monotone polygon, and line packing are presented. These algorithms achieve linear speedups on the pipelined hypercube, and provably optimal speedups on the shuffle-exchange and the cube-connected-cycles for any number p of processors satisfying 1>