Improved universal k-selection in hypercubes

Hong Shen

doi:10.1016/0167-8191(92)90076-J

Improved universal k-selection in hypercubes

Hong Shen

Åbo Akademi University

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

11 Citations (Scopus)

Abstract

This paper presents an improved algorithm for universal k-selection in hypercubes. The algorithm has a worst-case time complexity of O(n/p log p log (kp)/n) for selecting k smallest numbers from n given numbers in a hypercube of p processors (p≤n). This result shows a maximum speedup of O(log k) over the known result for the same problem in the case kp = O(n).

Original language	English
Pages (from-to)	177-184
Number of pages	8
Journal	Parallel Computing
Volume	18
Issue number	2
DOIs	https://doi.org/10.1016/0167-8191(92)90076-J
Publication status	Published - Feb 1992
Externally published	Yes

Keywords

Parallel algorithm
hypercube
processors
time complexity
universal k-selection

Access to Document

10.1016/0167-8191(92)90076-J

Cite this

@article{43c4ef48f2ad4146b1f650ed00ee3879,

title = "Improved universal k-selection in hypercubes",

abstract = "This paper presents an improved algorithm for universal k-selection in hypercubes. The algorithm has a worst-case time complexity of O(n/p log p log (kp)/n) for selecting k smallest numbers from n given numbers in a hypercube of p processors (p≤n). This result shows a maximum speedup of O(log k) over the known result for the same problem in the case kp = O(n).",

keywords = "Parallel algorithm, hypercube, processors, time complexity, universal k-selection",

author = "Hong Shen",

year = "1992",

month = feb,

doi = "10.1016/0167-8191(92)90076-J",

language = "English",

volume = "18",

pages = "177--184",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier BV",

number = "2",

}

TY - JOUR

T1 - Improved universal k-selection in hypercubes

AU - Shen, Hong

PY - 1992/2

Y1 - 1992/2

N2 - This paper presents an improved algorithm for universal k-selection in hypercubes. The algorithm has a worst-case time complexity of O(n/p log p log (kp)/n) for selecting k smallest numbers from n given numbers in a hypercube of p processors (p≤n). This result shows a maximum speedup of O(log k) over the known result for the same problem in the case kp = O(n).

AB - This paper presents an improved algorithm for universal k-selection in hypercubes. The algorithm has a worst-case time complexity of O(n/p log p log (kp)/n) for selecting k smallest numbers from n given numbers in a hypercube of p processors (p≤n). This result shows a maximum speedup of O(log k) over the known result for the same problem in the case kp = O(n).

KW - Parallel algorithm

KW - hypercube

KW - processors

KW - time complexity

KW - universal k-selection

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

U2 - 10.1016/0167-8191(92)90076-J

DO - 10.1016/0167-8191(92)90076-J

M3 - Article

AN - SCOPUS:38249013979

SN - 0167-8191

VL - 18

SP - 177

EP - 184

JO - Parallel Computing

JF - Parallel Computing

IS - 2

ER -

Improved universal k-selection in hypercubes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this