Connected Components inO(log3/2 n) Parallel Time for the CREW PRAM

摘要

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.