2026-04-17T04:16:29Zhttps://recercat.cat/oai/request

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

00925njm 22002777a 4500 dc Benedí García, Daniel author Duch Brown, Amalia author Pasarella Sánchez, Ana Edelmira author 2025 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) À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 A stream processing-based algorithm for maintaining minimum spanning forests of evolving graphs