@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 <e1>p </e1> of processors satisfying 1 les;<e1>p</e1> les;<e1>n</e1>/((log<sup>3</sup><e1>n</e1>)(loglog <e1>n</e1>)<sup>2</sup>), where <e1>n</e1> 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.}
}
