A Comparison of Data-Parallel Algorithms for Connected Components

John Greiner
CMU-CS-93-191 August, 1993

59k compressed postscript

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.