article · International Journal of Foundations of Computer Science · 2005

RANDOMIZED SORTING ON THE POPS NETWORK

Cited by 0Abstract and details only

Abstract

Partitioned Optical Passive Stars (POPS) network has been presented recently as a desirable model of parallel computation. Several papers have been published that address fundamental problems on this architecture. The algorithms presented in this paper are valid for POPS(d,g) where d>g and use randomization. We present an algorithm that solves the problem of sparse enumeration sorting of d ∊ keys in [Formula: see text] time and hence performs better than previous algorithms. We also present algorithms that allow us to do stable sorting of integers in the range [1, log n] and [Formula: see text] in [Formula: see text] time. When g=n ∊ , for any constant 0<∊<½ this allows us to do sorting of integers in the range [1,n] in [Formula: see text] time. We finally use these algorithms to solve the problem of multiple binary search in the case where we have d ∊ keys in [Formula: see text] time and in the case where we have integer keys in the range [1,n] in [Formula: see text] time, when g=n ∊ , for some constant 0<∊<½.

Cite this paper

APA 7

Davila, J., & Rajasekaran, S. (2005). RANDOMIZED SORTING ON THE POPS NETWORK. International Journal of Foundations of Computer Science, 16(01), 105–116. https://doi.org/10.1142/s0129054105002899

MLA 9

Davila, Jaime, and Sanguthevar Rajasekaran. “RANDOMIZED SORTING ON THE POPS NETWORK.” International Journal of Foundations of Computer Science, vol. 16, no. 01, 2005, pp. 105–16, https://doi.org/10.1142/s0129054105002899.

Chicago

Davila, Jaime, and Sanguthevar Rajasekaran. 2005. “RANDOMIZED SORTING ON THE POPS NETWORK.” International Journal of Foundations of Computer Science 16 (01): 105–16. https://doi.org/10.1142/s0129054105002899.

Harvard

Davila, J. and Rajasekaran, S. (2005) ‘RANDOMIZED SORTING ON THE POPS NETWORK’, International Journal of Foundations of Computer Science, 16(01), pp. 105–116. Available at: https://doi.org/10.1142/s0129054105002899.

BibTeX

@article{davila2005randomized,
  title = {{RANDOMIZED SORTING ON THE POPS NETWORK}},
  author = {Davila, Jaime and Rajasekaran, Sanguthevar},
  journal = {International Journal of Foundations of Computer Science},
  volume = {16},
  number = {01},
  pages = {105--116},
  year = {2005},
  doi = {10.1142/s0129054105002899}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.