BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR91-160
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Connected Components in O(lg3/2|V|) Parallel Time for the CREW PRAM
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Johnson, Donald B.
AUTHOR:: Metaxas, Panagiotis
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1991
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR91-160.pdf
ABSTRACT::
	Computing the connected components of an undirected graph G =
(V,E) on |V| = n vertices and |E| = m edges is a fundamental
computational problem.  The best known parallel algorithm for the CREW
PRAM model runs on O(lg2n) time using n2/lg2n processors
[CLC82,HCS79].  For the CRCW PRAM model in which concurrent writing is
permitted, the best known algorithm runs in O(lg n) time using almost
(n+m)/lg n processors [SV82,CV86,AS87].  Unfortunately, simulating
this algorithm on the weaker CREW model increases its running time to
O(lg2n) [CDR86, KR90,Vis83].  We present here an efficient and simple
algorithm that runs in O(lg 3/2n) time using n+m CREW processors.
END:: ncstrl.dartmouthcs//TR91-160