An O (nlogn) Cost Parallel Algorithm for the Single Function Coarsest Partition Problem
A CRCW PRAM algorithm is presented for computing the coarsest refinement of a partition of a finite set S of n elements with respect to a function f on S. The algorithm requires O(n) processors, O(logn) time, and and O(nlogn) space in the worst case.
A. Apostolico et al., "An O (nlogn) Cost Parallel Algorithm for the Single Function Coarsest Partition Problem," Parallel Algorithms and Architectures, Springer Verlag, Jan 1987.
The definitive version is available at https://doi.org/10.1007/3-540-18099-0_30
Mathematics and Statistics
Article - Journal
© 1987 Springer Verlag, All rights reserved.