TY - JOUR
T1 - Efficient algorithms for list ranking and for solving graph problems on the hypercube
JF - Parallel and Distributed Systems, IEEE Transactions on
Y1 - 1990
A1 - Ryu,K. W.
A1 - JaJa, Joseph F.
KW - algorithm;hypercube
KW - algorithms;graph
KW - algorithms;linear
KW - algorithms;sorting;
KW - balancing;one-port
KW - basic
KW - communication;sorting;st-numbering;tree
KW - complexity;graph
KW - components;ear
KW - decomposition;graph
KW - evaluation;computational
KW - Expression
KW - graph
KW - problems;biconnected
KW - problems;hypercube
KW - ranking;load
KW - speedup;list
KW - theory;parallel
AB - A hypercube algorithm to solve the list ranking problem is presented. Let n be the length of the list, and let p be the number of processors of the hypercube. The algorithm described runs in time O(n/p) when n= Omega;(p ^{1+ epsi;}) for any constant epsi; gt;0, and in time O(n log n/p+log^{3} p) otherwise. This clearly attains a linear speedup when n= Omega;(p ^{1+ epsi;}). Efficient balancing and routing schemes had to be used to achieve the linear speedup. The authors use these techniques to obtain efficient hypercube algorithms for many basic graph problems such as tree expression evaluation, connected and biconnected components, ear decomposition, and st-numbering. These problems are also addressed in the restricted model of one-port communication
VL - 1
SN - 1045-9219
CP - 1
M3 - 10.1109/71.80127
ER -