# Connected Components

We are interested in the pragmatic aspects of parallel algorithms for finding
connected components. This work compares several CRCW algorithms and
optimizations of these algorithms. In particular, the fastest algorithm
tested was developed as part of this work and is a hybrid of the other
algorithms used. Comparisons have been made using
NESL on a Connection Machine 2 and a Cray Y-MP/C90.
Ongoing work is primarily in Fortran on multiple processors of the
Cray Y-MP/C90. The goal is to optimize the hybrid algorithm as much as
possible. This work is being driven partly by the DIMACS Challenge.

## Papers

A Comparison of Data-Parallel Algorithms for Connected Components,
by John Greiner, CMU-CS-93-191, Aug. 1993.
Paper and
abstract.
A Comparison of Parallel Algorithms for Connected Components,
by John Greiner, from the Sixth Annual ACM Symposium on Parallel Algorithms
and Architectures (SPAA), June 27-29, 1994.
Paper,
abstract,
slides, and
talk notes.

The technical report contains more details about the optimizations and code.
The conference paper contains more recent information, including the hybrid
algorithm. A book chapter version in preparation contains more explanation
about how the algorithms work.

## Code

A couple algorithms written in NESL:
Awerbuch and Shiloach's,
Hirschberg, Chandra, and Sarwate's.
The NESL code used in John Greiner's papers includes versions of

and some
routines common to these algorithms and
graph generation routines.
**Related Work**:
parallel vision and image processing articles in the
SEL-HPC High Performance Computing Archive

Up to the Irregular Algorithms page or John Greiner's
research.