An Optimal Randomised Logarithmic Time Connectivity Algorithm for the EREW PRAM

摘要

Improving a long chain of works, we obtain a randomised EREW PRAM algorithm for finding the connected components of a graphG=(V, E) withnvertices andmedges inO(log n) time using an optimal number ofO((m+n)/log n) processors. The result returned by the algorithm is always correct. The probability that the algorithm will not complete inO(log n) time iso(n−c) for anyc>0.