Sorting-based selection algorithms for hypercubic networks
Publication
, Journal Article
Berthomé, P; Ferreira, A; Maggs, BM; Perennes, S; Plaxton, CG
Published in: Algorithmica (New York)
January 1, 2000
This paper presents several deterministic algorithms for selecting the kth largest record from a set of n records on any n-node hypercubic network. All of the algorithms are based on the selection algorithm of Cole and Yap, as well as on various sorting algorithms for hypercubic networks. Our fastest algorithm runs in O(lg n lg* n) time, very nearly matching the trivial Ω(lg n) lower bound. Previously, the best upper bound known for selection was O(lg n lg lg n). A key subroutine in our O(lg n lg* n) time selection algorithm is a sparse version of the Sharesort algorithm that sorts n records using p processors, p ≥ n, in O (lg n (lg lg p - lg lg(p/n))2) time.
Duke Scholars
Published In
Algorithmica (New York)
DOI
ISSN
0178-4617
Publication Date
January 1, 2000
Volume
26
Issue
2
Start / End Page
237 / 254
Related Subject Headings
- Computation Theory & Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Berthomé, P., Ferreira, A., Maggs, B. M., Perennes, S., & Plaxton, C. G. (2000). Sorting-based selection algorithms for hypercubic networks. Algorithmica (New York), 26(2), 237–254. https://doi.org/10.1007/s004539910011
Berthomé, P., A. Ferreira, B. M. Maggs, S. Perennes, and C. G. Plaxton. “Sorting-based selection algorithms for hypercubic networks.” Algorithmica (New York) 26, no. 2 (January 1, 2000): 237–54. https://doi.org/10.1007/s004539910011.
Berthomé P, Ferreira A, Maggs BM, Perennes S, Plaxton CG. Sorting-based selection algorithms for hypercubic networks. Algorithmica (New York). 2000 Jan 1;26(2):237–54.
Berthomé, P., et al. “Sorting-based selection algorithms for hypercubic networks.” Algorithmica (New York), vol. 26, no. 2, Jan. 2000, pp. 237–54. Scopus, doi:10.1007/s004539910011.
Berthomé P, Ferreira A, Maggs BM, Perennes S, Plaxton CG. Sorting-based selection algorithms for hypercubic networks. Algorithmica (New York). 2000 Jan 1;26(2):237–254.
Published In
Algorithmica (New York)
DOI
ISSN
0178-4617
Publication Date
January 1, 2000
Volume
26
Issue
2
Start / End Page
237 / 254
Related Subject Headings
- Computation Theory & Mathematics