Jf. Jaja et Kw. Ryu, AN EFFICIENT PARALLEL ALGORITHM FOR THE SINGLE FUNCTION COARSEST PARTITION PROBLEM, Theoretical computer science, 129(2), 1994, pp. 293-307
Citations number
20
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
We describe an efficient parallel algorithm to solve the single functi
on coarsest partition problem. The algorithm runs in O(log n) time usi
ng O(n log log n) operations on the arbitrary CRCW PRAM. The previous
best-known algorithms run in O(log2 n) time using 0(n log2 n) operatio
ns on the CREW PRAM, and O(log n) time using 0(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 ord
ering and to sort lexicographically a fist of strings of different len
gths.