Finding Connected Components in O(log n log log n) Time on the EREW PRAM

Abstract

In this paper, a parallel algorithm for finding the connected components of an undirected graph is presented. On a graph with n vertices and m edges, the algorithm runs in O(log n log log n) time using n + m processors on an EREW (exclusive-read and exclusive-write) PRAM. Prior to our work, the best exclusive-write algorithm known for this problem required O(log1.5n) time using n + m processors (D. B. Johnson and P. Metaxas, in "Proceedings 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 688-697; D. R. Karger, N. Nisan, and M. Parnas, in "Proceedings 4th Annual ACM Symposium on Parallel Architectures and Algorithms, 1992," pp. 373-381; N. Nisan, S. Szemerdi, and A. Wigderson, in "Proceedings 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992," pp. 24-29). © 1995 Academic Press. All rights reserved.