TY - GEN

T1 - Efficient parallel algorithms for some integer problems

AU - Zhang, Weixiong

AU - Wen, Zhaofang

N1 - Publisher Copyright:
© 1991 ACM.

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 -