CMU-CS-93-191 August, 1993

**Abstract:**
This paper presents a pragmatic comparison of three parallel algorithms
for finding connected components, together with optimizations on these
algorithms. Those being compared are two similar algorithms by Awerbuch
and Shiloach, and by Shiloach and Vishkin, and a randomized contraction
algorithm by Blelloch, based on algorithms by Reif and Phillips. Major
improvements are given for the first two which significantly reduces the
super-linear component of their work complexity. An improvement is also
given for the randomized algorithm, and this algorithm is shown to be
the fastest of those tested. These comparisons are presented with NESL
data-parallel code as executed on a Connection Machine CM-2.