An optimally efficient selection algorithm

Richard John Cole

doi:10.1016/0020-0190(88)90186-X

An optimally efficient selection algorithm

Richard John Cole

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

We give an optimally efficient parallel algorithm for selection on the EREW PRAM. It requires a linear number of operations and O(log n log^*n) time. A modification of the algorithm runs on the CRCW PRAM. It requires a linear number of operations and O(log n log^*/log log n) time.

Original language	English (US)
Pages (from-to)	295-299
Number of pages	5
Journal	Information Processing Letters
Volume	26
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(88)90186-X
State	Published - Jan 25 1988

Keywords

Selection
optimal algorithm
parallel algorithm

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(88)90186-X

Cite this

@article{515722c06f254cdeb8b94bf15d09e76d,

title = "An optimally efficient selection algorithm",

abstract = "We give an optimally efficient parallel algorithm for selection on the EREW PRAM. It requires a linear number of operations and O(log n log*n) time. A modification of the algorithm runs on the CRCW PRAM. It requires a linear number of operations and O(log n log*/log log n) time.",

keywords = "Selection, optimal algorithm, parallel algorithm",

author = "Cole, {Richard John}",

note = "Funding Information: * This research was partially supported by the National Sci-ence Foundation under Grants Nos. DCR-84-01633 and CCR-8702271, by an IBM faculty development award, and by ONR Grant No. NOOO14-85-K-0046.",

year = "1988",

month = jan,

day = "25",

doi = "10.1016/0020-0190(88)90186-X",

language = "English (US)",

volume = "26",

pages = "295--299",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - An optimally efficient selection algorithm

AU - Cole, Richard John

N1 - Funding Information: * This research was partially supported by the National Sci-ence Foundation under Grants Nos. DCR-84-01633 and CCR-8702271, by an IBM faculty development award, and by ONR Grant No. NOOO14-85-K-0046.

PY - 1988/1/25

Y1 - 1988/1/25

N2 - We give an optimally efficient parallel algorithm for selection on the EREW PRAM. It requires a linear number of operations and O(log n log*n) time. A modification of the algorithm runs on the CRCW PRAM. It requires a linear number of operations and O(log n log*/log log n) time.

AB - We give an optimally efficient parallel algorithm for selection on the EREW PRAM. It requires a linear number of operations and O(log n log*n) time. A modification of the algorithm runs on the CRCW PRAM. It requires a linear number of operations and O(log n log*/log log n) time.

KW - Selection

KW - optimal algorithm

KW - parallel algorithm

UR - http://www.scopus.com/inward/record.url?scp=0023826413&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023826413&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(88)90186-X

DO - 10.1016/0020-0190(88)90186-X

M3 - Article

AN - SCOPUS:0023826413

SN - 0020-0190

VL - 26

SP - 295

EP - 299

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

An optimally efficient selection algorithm

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this