AN EFFICIENT PARALLEL ALGORITHM FOR THE SINGLE FUNCTION COARSEST PARTITION PROBLEM

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.