A PROCESSOR EFFICIENT CONNECTIVITY ALGORITHM ON RANDOM GRAPHS

In this paper we present a randomized parallel algorithm for finding the connected components of a random input graph with n vertices in which the edges are chosen with probability p such that [Formula: see text]. The algorithm has O(log 2 n) expected time using only O(n) processors on the EREW PRAM... View More