2012/05/01 by Anastasios Katsigiannis, Nikos Anastopoulos, Konstantinos Nikas +1 · 1 citation
Computer Science · Mathematics · #Graph Theory and Algorithms #Data Management and Algorithms #Parallel Computing and Optimization Techniques #Kruskal's algorithm #Computer science #Parallel computing #Threading (protein sequence) #Scheme (mathematics) #Parallelism (grammar) #Algorithm #Graph #Minimum spanning tree #Theoretical computer science #Mathematics
paper · doi:10.1109/ipdpsw.2012.201
openalex publication_date 2012/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In this paper we present a Helper Threading scheme used to parallelize efficiently Kruskal's Minimum Spanning Forest algorithm. This algorithm is known for exhibiting inherently sequential characteristics. More specifically, the strict order by which the algorithm checks the edges of a given graph is the main reason behind the lack of explicit parallelism. Our proposed scheme attempts to overcome the imposed restrictions and improve the performance of the algorithm. The results show that for a wide range of graphs of varying structure, size and density the parallelization of Kruskal's algorithm is feasible. Observed speedups reach up to 5.5 for 8 running threads, revealing the potentials of our approach.