Finding the connected components of an undirected graphG=(V, E) onn=|V| vertices andm=|E| edges is a fundamental computational problem. The best known parallel algorithm for the CREW PRAM model runs inO(log2 n) time usingn2/log2 nprocessors. For the CRCW PRAM model, in which concurrent writing is permitted, the best known algorithm runs inO(log n) time using slightly more than (n+m)/log nprocessors. Simulating this algorithm on the weaker CREW model increases its running time toO(log2 n). We present here a simple algorithm that runs inO(log3/2 n) time usingn+mCREW processors. Finding ano(log2 n) parallel connectivity algorithm for this model was an open problem for many years.
No takes yet. Share an insight, caveat, or question.
Johnson et al. (1997) studied this question.