An O (nlogn) Cost Parallel Algorithm for the Single Function Coarsest Partition Problem

Author

Alberto Apostolico
Costas S. Iliopoulos
Robert Paige L., Missouri University of Science and TechnologyFollow

Abstract

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.

Recommended Citation

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

Department(s)

Mathematics and Statistics

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1987 Springer Verlag, All rights reserved.

Publication Date

01 Jan 1987