A parallel median algorithm

Richard Cole; Chee K. Yap

doi:10.1016/0020-0190(85)90080-8

A parallel median algorithm

Richard Cole, Chee K. Yap

Computer Science

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

Abstract

We give a deterministic algorithm for finding the kth smallest item in a set of n items, running in O((log log n)²) parallel time on O(n) processors in Valiant's comparison model.

Original language	English (US)
Pages (from-to)	137-139
Number of pages	3
Journal	Information Processing Letters
Volume	20
Issue number	3
DOIs	https://doi.org/10.1016/0020-0190(85)90080-8
State	Published - Apr 8 1985

Keywords

Parallel algorithm
comparison model
median
selection

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(85)90080-8

Cite this

@article{2d9b3074b35440a28490d096ff960c06,

title = "A parallel median algorithm",

abstract = "We give a deterministic algorithm for finding the kth smallest item in a set of n items, running in O((log log n)2) parallel time on O(n) processors in Valiant's comparison model.",

keywords = "Parallel algorithm, comparison model, median, selection",

author = "Richard Cole and Yap, {Chee K.}",

note = "Funding Information: Subsequently, Megiddo \[2\]h as shown that fast parallel algorithms can aid in the design of efficient sequential algorithms. In the several examples he gives, the communication costs of the parallel algorithms can be ignored; that is, the * This work was partially supported by the Natural Science Foundation under Grant DCR-84-01633.",

year = "1985",

month = apr,

day = "8",

doi = "10.1016/0020-0190(85)90080-8",

language = "English (US)",

volume = "20",

pages = "137--139",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - A parallel median algorithm

AU - Cole, Richard

AU - Yap, Chee K.

N1 - Funding Information: Subsequently, Megiddo \[2\]h as shown that fast parallel algorithms can aid in the design of efficient sequential algorithms. In the several examples he gives, the communication costs of the parallel algorithms can be ignored; that is, the * This work was partially supported by the Natural Science Foundation under Grant DCR-84-01633.

PY - 1985/4/8

Y1 - 1985/4/8

N2 - We give a deterministic algorithm for finding the kth smallest item in a set of n items, running in O((log log n)2) parallel time on O(n) processors in Valiant's comparison model.

AB - We give a deterministic algorithm for finding the kth smallest item in a set of n items, running in O((log log n)2) parallel time on O(n) processors in Valiant's comparison model.

KW - Parallel algorithm

KW - comparison model

KW - median

KW - selection

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

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

U2 - 10.1016/0020-0190(85)90080-8

DO - 10.1016/0020-0190(85)90080-8

M3 - Article

AN - SCOPUS:0022421085

SN - 0020-0190

VL - 20

SP - 137

EP - 139

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

A parallel median algorithm

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this