2026-04-13T07:37:27Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/1063682026-01-29T02:20:20Zcom_2072_1033col_2072_452950

A systolic algorithm for the fast computation of the connected components of a graph Núñez, Fernando J. Valero Cortés, Mateo Àrees temàtiques de la UPC::Informàtica::Arquitectura de computadors Parallel algorithms Multiprocessors Cellular arrays Computer architecture Multiprocessing systems Algorismes paral·lels Multiprocessadors 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) 1988 Conference report http://ieeexplore.ieee.org/document/15396/ Open Access Institute of Electrical and Electronics Engineers (IEEE)