• 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.

  Postscript Compressed Postscript
  Back to other publications

  Back to my home page