In this paper, we present randomized algorithms for selection on the h
ypercube. We identify two variants of the hypercube, namely, the seque
ntial model and the parallel model. In the sequential model, any node
at any time can handle only communication along a single incident edge
, whereas in the parallel model a node can communicate along all its i
ncident edges at the same time. We specify three variations of the par
allel model and present optimal randomized algorithms on all these thr
ee versions of parallel model. In particular, we show that selection o
n an input of size n can be performed on a p-node hypercube in time O(
(n/p) + log p) with high probability, on any of the three versions of
the parallel model. This result is important in view of a lower bound
that implies that selection needs Omega((n/p)log log p + log p) time o
n a p-node sequential hypercube. We modify our selection algorithm to
run on the sequential hypercube in which case it runs in an expected t
ime nearly matching this lower bound. For the special case when a = p,
our selection algorithm runs in an optimal O(log n) time on the seque
ntial hypercube. Our algorithms are very simple and are most likely to
perform well in practice. (C) 1996 Academic Press, Inc.