2026-04-17T23:00:45Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/4600582026-04-08T11:27:02Zcom_2072_1033col_2072_452950

A stream processing-based algorithm for maintaining minimum spanning forests of evolving graphs Benedí García, Daniel Duch Brown, Amalia Pasarella Sánchez, Ana Edelmira Universitat Politècnica de Catalunya. Departament de Ciències de la Computació Universitat Politècnica de Catalunya. ALBCOM - Algorísmia, Bioinformàtica, Complexitat i Mètodes Formals Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat Spanning trees Kruskal algorithm Stream processing Evolving graphs Dynamic pipeline approach In this work we introduce a concurrent/parallel adaptation of Kruskal algorithm based on the dynamic pipeline approach. This is, the input (undirected) graph is given by a stream of weighted edges and it is dynamically created and maintained in a distributed way along a pipeline of stateful stages. To be concrete, firstly an initial graph is created and then, whenever the graph evolves because of edges are added, removed or updated, the minimum spanning tree (forest) according to the current graph can be computed and output immediately. Moreover, we provide a working implementation in the Go programming language. Go is suitable to dynamic pipelines’ implementations thanks to its communication channels and co-routines. We show experimentally that our algorithm scales well to a large number of processes and that it is competitive against the classic sequential Kruskal algorithm and a well known parallelized version of the Kruskal algorithm. Our experimental study is done for a large class of dynamic random graphs –including several densities and sizes– and some real dynamic graphs. This work has been funded by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21. Peer Reviewed Postprint (published version) 2025 Conference report Benedi, D.; Duch, A.; Pasarella, E. A stream processing-based algorithm for maintaining minimum spanning forests of evolving graphs. A: Alberto Mendelzon International Workshop on Foundations of Data Management. «Proceedings of the 16th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2024): Mexico City, Mexico, October 2-4, 2024». CEUR-WS.org, 2025. ISSN 1613-0073. 1613-0073 https://hdl.handle.net/2117/460058 eng https://ceur-ws.org/Vol-3954/ info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2020-112581GB-C21/ES/MODELOS Y TECNICAS PARA EL PROCESAMIENTO DE INFORMACION A GRAN ESCALA -- BARCELONA/ http://creativecommons.org/licenses/by/4.0/ Open Access Attribution 4.0 International 12 p. application/pdf CEUR-WS.org