TY - JOUR
T1 - An efficient parallel algorithm for the single function coarsest partition problem
JF - Theoretical computer science
Y1 - 1994
A1 - JaJa, Joseph F.
A1 - Ryu,K. W.
AB - We describe an efficient parallel algorithm to solve the single function coarsest partition problem. The algorithm runs in O(log n) time using O(n log log n) operations on the arbitrary CRCW PRAM. The previous best-known algorithms run in O(log2 n) time using O(n log2 n) operations on the CREW PRAM, and O(log n) time using O(n log n) operations on the arbitrary CRCW PRAM. Our solution is based on efficient algorithms for solving several subproblems that are of independent interest. In particular, we present efficient parallel algorithms to find a minimal starting point of a circular string with respect to lexicographic ordering and to sort lexicographically a list of strings of different lengths
VL - 129
CP - 2
ER -