An Approach to Parallelize Kruskal's Algorithm Using Helper Threads

Citations Over Time

Abstract

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.

Related Papers

• → Threading with explicit models for evolutionary conservation of structure and sequence(1999)18 cited
• Generation of pseudonative protein structures for threading.(1997)
• → Generation of pseudonative protein structures for threading(1997)4 cited
• The Realization and Analysis of Kruskal's Algorithm(2008)
• → Structure Prediction: Threading(2003)