Optimal parallel multiselection on EREW PRAM

Hong Shen

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


Multiselection requires to select r elements at specified ranks in a given set of n elements, r ≤ n. This paper proposes a paradigm for parallel multiselection to achieve the optimal cost. Following this paradigm and employing a cost-optimal algorithm for single-element selection, a cost-optimal parallel algorithm for multiselection is presented. Our algorithm runs in O(n; log r) time on an EREW PRAM with n1-∈ processors for any 0 < ∈ < 1. In the special case when ∈ = log(log n log * n)/log n, our algorithm requires O(log n log * n log r) time and O(n log r) cost.

Original languageEnglish
Pages (from-to)1987-1992
Number of pages6
JournalParallel Computing
Issue number13
Publication statusPublished - 15 Dec 1997
Externally publishedYes


  • Multiselection
  • Parallel algorithm
  • Selection
  • Sorting


Dive into the research topics of 'Optimal parallel multiselection on EREW PRAM'. Together they form a unique fingerprint.

Cite this