An optimal randomized parallel algorithm for finding connected components in a graph
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 492-501
- https://doi.org/10.1109/sfcs.1986.9
Abstract
We present a parallel randomized algorithm for finding the connected components of an undirected graph. Our algorithm takes T = O(log (n)) time and p = O(m+n/(log(n) processors, where m = number of edges and n = number of vertices. This algorithm improves the results of Cole and Vishkin1, which use O(log (n)·log (log (n))· log (log (log (n)))) time. Our algorithm is Optimal in the sense that the product P·T is a linear function of the input size. The algorithm requires O(m + n) space which is the input size, so it is Optimal in space as well.Keywords
This publication has 3 references indexed in Scilit:
- Parallel tree contraction and its applicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- An O(logn) parallel connectivity algorithmJournal of Algorithms, 1982
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952