- 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)
- Back to other
- Back to my home page