A PRAM ALGORITHM FOR A SPECIAL CASE OF THE SET PARTITION PROBLEM

Abstract

We consider the special case of the two functions coarsest partitioning problem, where one of the functions is a cyclic permutation and the other arbitrary. Here we present a parallel algorithm on a CRCW PRAM that solves the above partitioning problem in O(α(n)log(β(n))) time using O(n) processors, where n is the set cardinality, β(n) is the number of distinct prime factors of n, and α(n) is the sum of the exponents of the primes in the factorization of n. In almost all cases the algorithm runs in O(loglognlogloglogn) time with n processors.

KEY WORDS:

• Analysis of algorithms
• design of algorithms
• parallel algorithms

Additional information

Notes on contributors

CLIVE N. GALLEY

The author was supported by the 91809000 Science and Engineering Research Council Postgraduate Studentship. The author was also partially supported by a Universily of London Central Research Fund grant.

COSTAS S. ILIOPOULOS

The author acknowledges the support of the UK Science and Engineering Research Council grant number GR/F 00898 during the course of this research. The author was also partially supported by NATO grant CRG 900293, by the ESPRIT BRA grant 7141 (ALCOM II) and by the G9115730 Medical Research Council grant.