Sorting-based selection algorithms for hypercubic networks
Publication
, Conference
Berthome, P; Ferreira, A; Maggs, BM; Perennes, S; Plaxton, CG
Published in: Proceedings of 7th International Parallel Processing Symposium, IPPS 1993
January 1, 1993
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 (1985), as well as on various sorting algorithms for hypercubic networks. The authors fastest algorithm runs in O(lg n lgn) time, very nearly matching the trivial Omega (lg n) lower bound. Previously, the best upper bound known for selection was O(lg n lg lg n).
Duke Scholars
Published In
Proceedings of 7th International Parallel Processing Symposium, IPPS 1993
DOI
Publication Date
January 1, 1993
Start / End Page
89 / 95
Citation
APA
Chicago
ICMJE
MLA
NLM
Berthome, P., Ferreira, A., Maggs, B. M., Perennes, S., & Plaxton, C. G. (1993). Sorting-based selection algorithms for hypercubic networks. In Proceedings of 7th International Parallel Processing Symposium, IPPS 1993 (pp. 89–95). https://doi.org/10.1109/IPPS.1993.262861
Berthome, P., A. Ferreira, B. M. Maggs, S. Perennes, and C. G. Plaxton. “Sorting-based selection algorithms for hypercubic networks.” In Proceedings of 7th International Parallel Processing Symposium, IPPS 1993, 89–95, 1993. https://doi.org/10.1109/IPPS.1993.262861.
Berthome P, Ferreira A, Maggs BM, Perennes S, Plaxton CG. Sorting-based selection algorithms for hypercubic networks. In: Proceedings of 7th International Parallel Processing Symposium, IPPS 1993. 1993. p. 89–95.
Berthome, P., et al. “Sorting-based selection algorithms for hypercubic networks.” Proceedings of 7th International Parallel Processing Symposium, IPPS 1993, 1993, pp. 89–95. Scopus, doi:10.1109/IPPS.1993.262861.
Berthome P, Ferreira A, Maggs BM, Perennes S, Plaxton CG. Sorting-based selection algorithms for hypercubic networks. Proceedings of 7th International Parallel Processing Symposium, IPPS 1993. 1993. p. 89–95.
Published In
Proceedings of 7th International Parallel Processing Symposium, IPPS 1993
DOI
Publication Date
January 1, 1993
Start / End Page
89 / 95