Advanced search
Publication Cover
International Journal of Computer Mathematics Volume 80, 2003 - Issue 2
Submit an article Journal homepage
27
Views
3
CrossRef citations to date
0
Altmetric
Original Articles

Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers

Hong Shen Graduate School of Information Science, Japan Advanced Institute of Science and Technology, Tatsunokuchi, Ishikawa, 923-1292, Japan
,
Yijie Han Computer Science and Telecommunication Program, University of Missouri, Kansas City, Kansas City, MO, 64110-2499, USA
,
Yi Pan Department of Computer Science, Georgia State University, Atlanta, GA, 30303, USA
&
David Evans Department of Computing, The Nottingham Trent University, Burton Street, Nottingham, NG1 4BU, UK
Pages 165-179 | Published online: 15 Sep 2010

  • Akl , S. G. 1984 . An optimal algorithm for parallel selection . Information Processing Letters , : 19
  • Blum , M , Floyd , R. W. , Pratt , V R. , Rivest , R. L. and Tarjan , R. E. 1972 . Time bounds for selection . J. Comput. Syst. Sci. , 7 : 448 – 461 .
  • Chaudhuri , S. , Hagerup , T. and Raman , R. Approximate and exact deterministic parallel selection . Proc. Mathematical Foundations of Computer Science . 1993 . Springer-Verlag .
  • Chen , G. L. and Shen , H. Bitonic selection algorithm on simd machines . Proc. 2nd Intern. Conference on Computers and Applications . pp. 176 – 182 . IEEE CS Press .
  • Chen , G. L. and Shen , H. 1987 . Bitonic selection network and bitonic selection algorithm on multiprocessors . Computer Studies and Development , 24 : 1 – 10 .
  • Cole , R. and Yap , C. K. 1985 . A parallel median algorithm . Information processing Letters , 20 : 137 – 439 .
  • Cole , R. J. 1988 . An optimally efficient selection algorithm . Information Processing Letters , 26 : 295 – 299 .
  • Fredman , M L. and Spencer , T. H. 1987 . Refined complexity analysis for heap operations . Journal of Computer and System Sciences , : 269 – 284 .
  • Fussenegger , F. and Johnson , D. B. 1979 . A counting approach to lower bounds for selection problems . J. Asso. Comput Mach. , 26 : 540 – 543 .
  • Hyafil , L. 1976 . Bounds for selection . SIAMJ. Compta. , 5 : 114 – 119 .
  • Batcher , K. E. Sorting networks and their applications . Proc. AFIPS 1968 Spring Joint Computer Conference . pp. 307 – 314 . AFIPS Press .
  • Kirkpatrick , D. G. 1981 . A unified lower bound for selection and set partitioning problems . J. Asso. Comput. Mach. , 28 : 150 – 165 .
  • Krizanc , D. and Narayanan , L. Multiple-packet selection on mesh-connected processor arrays . Proc. 1992 Intern. Parallel Processing Symp. (IPPS'92} . pp. 602 – 605 . IEEE CS Press .
  • Kunde , M. Routing and sorting on mesh-connected architectures . Proc. Agean Workshop on Computing: VLSI algorithms and architectures . pp. 423 – 433 . Lecture Notes on Computer Science
  • Kunde , M. 1989 . l-selection and related problems on grids of processors . J. of New Generation Computer Systems , 2 : 129 – 143 .
  • Plaxton , C. G. August 1989 . On the network complexity of selection , Technical Report STAN//CS-TR89-1276 August , Stanford University, Department of Computer Science .
  • Pratt , V R. and Yao , F. F. 1973 . On lower bounds for computing the ith largest element , Iowa City : Proc. Annual Symp. Switching and Atomata Theory .
  • Schnorr , C. and Shamir , A. An optimal sorting algorithm for mesh-connected computers . Proc. 1996 Symp. Theory of Computing (STOC'86} . pp. 255 – 263 . ACM .
  • Schonhage , A. , Paterson , M. and Pippenger , N. 1976 . Finding the median . J. Comput. Syst. Sci. , 13 : 184 – 199 .
  • Shen , H. 1992 . Improved universal k-selection in hypercubes . Parallel Computing , 18 : 177 – 184 .
  • Shen , H. Efficient parallel multiselection in hypercubes . In: Proc. 1997 Intern. Symp. on Parallel Architectures, Algorithms and Networks (I-SPAN'97} . IEEE CS Press . page to appear
  • Shen , H. 1997 . Optimal parallel multiselection on EREW PRAM . Parallel Computing , 188 : 287 – 298 .
  • Shen , H. and Chen , G. L. 1990 . A new upper bound of delay time in selection network . Chinese Journal of Computers , 13 : 88 – 100 .
  • Stone , H. 1971 . Parallel processing with the perfect shuffle . IEEE Trans. Comput. , C-20 (2} ) : 153 – 161 .
  • Yap , C. K. 1976 . New bounds for selection. Comm . ACM , 19 : 501 – 508 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.