A bitonic selection algorithm on multiprocessor system

Guoliang Chen, Hong Shen

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


The so-called (m, n) selection problem is defined as the selection of the m smallest (or largest) numbers from n given numbers (n>m). Solving this problem in parallel mode has been successful on the networks, but it is seldom studied on the multiprocessor systems. This paper first, based on Batcher's principle of bitonic merging, proposes the bitonic selection network. Then it repeals the varying rule of the pivots in all successive ranks of the network through our observation to the data transfer property in the network. Finally, according to this rule, the parallel selection algorithm with running time O (log nlog m)1) on n processors is presented.

Original languageEnglish
Pages (from-to)315-322
Number of pages8
JournalJournal of Computer Science and Technology
Issue number4
Publication statusPublished - Oct 1989
Externally publishedYes


Dive into the research topics of 'A bitonic selection algorithm on multiprocessor system'. Together they form a unique fingerprint.

Cite this