ABSTRACT

This paper presents a comparison of the pragmatic aspects of some parallel algorithms for finding connected compo- nents, together with optimizations on these algorithms. The algorithms being compared are two similar algorithms by Shiloach-Vishkin [22] and Awerbuch-Shiloach [2], a random- ized contraction algorithm based on algorithms by Reif [21] and Phillips [20], and a hybrid algorithm [11]. Improve- ments 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.