RANDOMIZED SELECTION ON THE HYPERCUBE

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.