FINDING CONNECTED COMPONENTS IN O(LOG-N LOG LOG-N) TIME ON THE EREW PRAM

In this paper, a parallel algorithm for finding the connected components of an undirected graph is presented. On a graph with n vertices and n 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(log(1.5) n) 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). (C) 1995 Academic Press, Inc.