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

研究成果: Article › 同行評審

11 引文斯高帕斯（Scopus）

摘要

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).

原文	English
頁（從 - 到）	177-184
頁數	8
期刊	Parallel Computing
卷	18
發行號	2
DOIs	https://doi.org/10.1016/0167-8191(92)90076-J
出版狀態	Published - 2月 1992
對外發佈	是

存取文件

10.1016/0167-8191(92)90076-J

其它文件與鏈接

Link to publication in Scopus

引用此

@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 - https://www.scopus.com/pages/publications/38249013979

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

摘要

存取文件

其它文件與鏈接

指紋

引用此