A systolic algorithm for the fast computation of the connected components of a graph

Abstract

The authors consider the description of a systolic algorithm to solve the connected-component problem. It is executed in a ring topology with N processors, requiring O(Nlog N) time without regard to the graph's sparsity. The algorithm-partitioning issue is also addressed, indicating how to optimally map the computations into fixed-size rings or linear arrays. The proposed algorithm leads to simple processing elements, data addressing, and control. These points make the systolic array highly implementable.

Peer Reviewed

Postprint (published version)