Open AccessAn Efficient Parallel Algorithm for the Single Function Coarsest Partition Problem on the EREW PRAM
Author(s) -
Haa KyeoungJu,
Ku KyoMin,
Park HaeKyeong,
Kim YoungKook,
Ryu KwanWoo
Publication year - 1999
Publication title -
etri journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.295
H-Index - 46
eISSN - 2233-7326
pISSN - 1225-6463
DOI - 10.4218/etrij.99.0199.0203
Subject(s) - partition (number theory) , parallel algorithm , parallel computing , partition problem , computer science , function (biology) , algorithm , constant (computer programming) , binary logarithm , running time , discrete mathematics , mathematics , combinatorics , evolutionary biology , biology , programming language
In this paper, we derive an efficient parallel algorithm to solve the single function coarsest partition problem. This algorithm runs in O ( log2n ) time using O ( nlogn ) operations on the EREW PRAM with O ( n ) memory cells used. Compared with the previous PRAM algorithms that consume O(n1+ ε ) memory cells for some positive constant ε > 0, our algorithm consumes less memory cells without increasing the total number of operations.