A comparison of parallel algorithms for connected components

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