A Comparison of Data-Parallel Algorithms for Connected Components

SPAA version: 50k compressed postscript
TR version: 59k compressed postscript

Abstract: 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 and Awerbuch-Shiloach, a randomized contraction algorithm based on algorithms by Reif and Phillips, and a hybrid algorithm. 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 code as executed on a Connection Machine~2 and Cray Y-MP/C90.

Note: This online copy has corrected the last line of each of Figures 1 and 4 from the published version.

@inproceedings{spaa-concomp,
	author = "John Greiner",
	title = "A Comparison of Data-Parallel Algorithms for Connected
		 Components",
        booktitle = "Proceedings Symposium on 
                Parallel Algorithms and Architectures",
	address = "Cape May, NJ",
        pages = "16--25",
	month = jun,
	year = 1994 }

@techreport{concomp,
	author = "John Greiner",
	title = "A Comparison of Data-Parallel Algorithms for Connected
		 Components",
	institution = "School of Computer Science, Carnegie Mellon University",
	number = "CMU-CS-93-191",
	month = aug,
	year = 1993 }