A comparison of parallel algorithms for connected components

This paper presents a comparison of the pragmatic aspects of some parallel algorithms for finding connected components, together with optimizations on these algorithms. The algorithms being compared are two similar algorithms by Shiloach-Vishkin 22 and Awerbuch-Shiloach 2, a randomized contraction algorithm based on algorithms by Reif 21 and Phillips 20, and a hybrid algorithm 11. Improvements are given for the first two to improve performance significantly, although without improving their asymptotic complexity. The hybrid combines features of the others and is generally the fastest of those tested. Timings were made using NESL 4 code as executed on a Connection Machine 2 and Cray Y-MP/C90.