Efficient parallel algorithms for some integer problems

Weixiong Zhang; Zhaofang Wen

doi:10.1145/327164.327169

Efficient parallel algorithms for some integer problems

Weixiong Zhang, Zhaofang Wen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

This paper considers parallel solutions to some problems with integers as input. We first discuss the general integer packing problem and propose a parallel algorithm for this problem on exclusive-read exclusivewrite parallel random-access machine (EREW PRAM). Then we present parallel algorithms on EREW PRAM for bucket sort, graph adjacency-list construction, integer element distinctness, integer set problems (including integer set disjointness, union and difference), and integer max gap. We hope that the address table and general integer packing algorithm proposed in this paper will have other applications in parallel algorithm design.

Original language	English
Title of host publication	CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science
Publisher	Association for Computing Machinery, Inc
Pages	11-20
Number of pages	10
ISBN (Print)	0897913825, 9780897913829
DOIs	https://doi.org/10.1145/327164.327169
State	Published - Apr 1 1991
Event	19th Annual Conference on Computer Science, CSC 1991 - San Antonio, United States Duration: Mar 4 1991 → Mar 7 1991

Publication series

Name	CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science

Conference

Conference	19th Annual Conference on Computer Science, CSC 1991
Country/Territory	United States
City	San Antonio
Period	03/4/91 → 03/7/91

Keywords

Bucket sort
EREW PRAM
General integer packing
Graph adjacency-list
Integer element distinctness
Integer max gap
Integer set problems
Parallel algorithm

Access to Document

10.1145/327164.327169

Cite this

@inproceedings{1e003cbc3ceb443a990903d9fd6334c2,

title = "Efficient parallel algorithms for some integer problems",

abstract = "This paper considers parallel solutions to some problems with integers as input. We first discuss the general integer packing problem and propose a parallel algorithm for this problem on exclusive-read exclusivewrite parallel random-access machine (EREW PRAM). Then we present parallel algorithms on EREW PRAM for bucket sort, graph adjacency-list construction, integer element distinctness, integer set problems (including integer set disjointness, union and difference), and integer max gap. We hope that the address table and general integer packing algorithm proposed in this paper will have other applications in parallel algorithm design.",

keywords = "Bucket sort, EREW PRAM, General integer packing, Graph adjacency-list, Integer element distinctness, Integer max gap, Integer set problems, Parallel algorithm",

author = "Weixiong Zhang and Zhaofang Wen",

note = "Publisher Copyright: {\textcopyright} 1991 ACM.; 19th Annual Conference on Computer Science, CSC 1991 ; Conference date: 04-03-1991 Through 07-03-1991",

year = "1991",

month = apr,

day = "1",

doi = "10.1145/327164.327169",

language = "English",

isbn = "0897913825",

series = "CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science",

publisher = "Association for Computing Machinery, Inc",

pages = "11--20",

booktitle = "CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science",

}

Zhang, W & Wen, Z 1991, Efficient parallel algorithms for some integer problems. in CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science. CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science, Association for Computing Machinery, Inc, pp. 11-20, 19th Annual Conference on Computer Science, CSC 1991, San Antonio, United States, 03/4/91. https://doi.org/10.1145/327164.327169

Efficient parallel algorithms for some integer problems. / Zhang, Weixiong; Wen, Zhaofang.
CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science. Association for Computing Machinery, Inc, 1991. p. 11-20 (CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient parallel algorithms for some integer problems

AU - Zhang, Weixiong

AU - Wen, Zhaofang

PY - 1991/4/1

Y1 - 1991/4/1

N2 - This paper considers parallel solutions to some problems with integers as input. We first discuss the general integer packing problem and propose a parallel algorithm for this problem on exclusive-read exclusivewrite parallel random-access machine (EREW PRAM). Then we present parallel algorithms on EREW PRAM for bucket sort, graph adjacency-list construction, integer element distinctness, integer set problems (including integer set disjointness, union and difference), and integer max gap. We hope that the address table and general integer packing algorithm proposed in this paper will have other applications in parallel algorithm design.

AB - This paper considers parallel solutions to some problems with integers as input. We first discuss the general integer packing problem and propose a parallel algorithm for this problem on exclusive-read exclusivewrite parallel random-access machine (EREW PRAM). Then we present parallel algorithms on EREW PRAM for bucket sort, graph adjacency-list construction, integer element distinctness, integer set problems (including integer set disjointness, union and difference), and integer max gap. We hope that the address table and general integer packing algorithm proposed in this paper will have other applications in parallel algorithm design.

KW - Bucket sort

KW - EREW PRAM

KW - General integer packing

KW - Graph adjacency-list

KW - Integer element distinctness

KW - Integer max gap

KW - Integer set problems

KW - Parallel algorithm

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

U2 - 10.1145/327164.327169

DO - 10.1145/327164.327169

M3 - Conference contribution

AN - SCOPUS:85055866720

SN - 0897913825

SN - 9780897913829

T3 - CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science

SP - 11

EP - 20

BT - CSC 1991 - Proceedings of the 19th Annual Conference on Computer Science

PB - Association for Computing Machinery, Inc

T2 - 19th Annual Conference on Computer Science, CSC 1991

Y2 - 4 March 1991 through 7 March 1991

ER -

Efficient parallel algorithms for some integer problems

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this