Distributed Large Minimum Spanning Tree Computation

In this paper we implement and compare four distributed algorithms for solving the Minimum Spanning Tree (MST) problem: edge partitioning, vertex partitioning and two versions of parallel prim. The main use scenarios for those algorithms are cases where the entirety of the graph does not fit into the main memory of a single machine. The basic assumption for all of them is, that just the graph vertices fit into the memory of each individual compute node. The idea thus is to scale linearly in problem size with the number of added distributed compute nodes running the algorithms.

The fulltext can be found here.

Authors: Abhimanyu Bhadauria, Nodar Ambroladze, Philipp Schaad (all ETH Zürich)