Computing connected components on parallel computers

TLDR

In shared‑memory parallel systems, concurrent fetches are allowed but concurrent stores are not. The authors propose a parallel algorithm that uses n² processors to compute the connected components of an undirected graph in O(log² n) time. The algorithm operates on a shared‑memory model with n² processors, computing connected components (and the transitive closure of symmetric Boolean matrices) in O(log² n) time. The same O(log² n) time bound can be achieved with fewer processors, namely n ⌈n/⌈log² n⌉⌉.

Abstract

We present a parallel algorithm which uses n 2 processors to find the connected components of an undirected graph with n vertices in time O (log 2 n ). An O (log 2 n ) time bound also can be achieved using only n ⌈ n /⌈log 2 n ⌉⌉ processors. The algorithm can be used to find the transitive closure of a symmetric Boolean matrix. We assume that the processors have access to a common memory. Simultaneous access to the same location is permitted for fetch instructions but not for store instructions.