@article {15000,
title = {Optimal algorithms on the pipelined hypercube and related networks},
journal = {Parallel and Distributed Systems, IEEE Transactions on},
volume = {4},
year = {1993},
month = {1993/05//},
pages = {582 - 591},
abstract = {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 les;p les;n/((log^{3}n)(loglog n)^{2}), where n is the input size. The lower bound results are established under no restriction on how the input is mapped into the local memories of the different processors},
keywords = {algorithms;pipeline, algorithms;pipelined, combinatorial, geometry;parallel, hypercube;shuffle-exchange;combinatorial, mathematics;computational, packing;monotone, polygon;parallel, problems;cube-connected-cycles;line, processing;},
isbn = {1045-9219},
doi = {10.1109/71.224210},
author = {JaJa, Joseph F. and Ryu,K. W.}
}