2026-04-18T02:20:43Zhttps://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 Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors Universitat Politècnica de Catalunya. CAP - Grup de Computació d'Altes Prestacions À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 Núñez, F., Valero, M. A systolic algorithm for the fast computation of the connected components of a graph. A: IEEE International Symposium on Circuits and Systems. "1988 IEEE International Symposium on Circuits and Systems: Espo, Finland, 7-9 June 1988". Espoo: Institute of Electrical and Electronics Engineers (IEEE), 1988, p. 2267-2270. https://hdl.handle.net/2117/106368 10.1109/ISCAS.1988.15396 eng http://ieeexplore.ieee.org/document/15396/ Open Access 4 p. application/pdf Institute of Electrical and Electronics Engineers (IEEE)