Optimal parallel multiselection on EREW PRAM

Hong Shen

研究成果: Article同行評審

5 引文 斯高帕斯(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.

原文English
頁(從 - 到)1987-1992
頁數6
期刊Parallel Computing
23
發行號13
DOIs
出版狀態Published - 15 12月 1997
對外發佈

指紋

深入研究「Optimal parallel multiselection on EREW PRAM」主題。共同形成了獨特的指紋。

引用此