Improved universal k-selection in hypercubes

Hong Shen

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


This paper presents an improved algorithm for universal k-selection in hypercubes. The algorithm has a worst-case time complexity of O(n/p log p log (kp)/n) for selecting k smallest numbers from n given numbers in a hypercube of p processors (p≤n). This result shows a maximum speedup of O(log k) over the known result for the same problem in the case kp = O(n).

Original languageEnglish
Pages (from-to)177-184
Number of pages8
JournalParallel Computing
Issue number2
Publication statusPublished - Feb 1992
Externally publishedYes


  • Parallel algorithm
  • hypercube
  • processors
  • time complexity
  • universal k-selection


Dive into the research topics of 'Improved universal k-selection in hypercubes'. Together they form a unique fingerprint.

Cite this