- Sorting-based selection algorithms for hypercubic
networks. P. Berthome, A. Ferreira, B. M. Maggs, S. Perennes, and
C. G. Plaxton, Algorithmica, Volume 26, Number 2, 2000, pp. 237-254.
- This paper presents a deterministic algorithm for selecting the k'th largest record from a set of n records on an n-node hypercube, butterfly, or shuffle-exchange network in O(log n log* n) time. The fastest previously known algorithm required O(log n loglog n) time.

**Back to other publications****Back to my home page**