Communication-Optimal Parallel Minimum Spanning Tree Algorithms (Extended Abstract)

Lower and upper bounds for finding a minimum spanning tree (MST) in a weighted undirected graph on the BSP model are presented. We provide the first non-trivial lower bounds on the communication volume required to solve the MST problem. Let p denote the number of processors, n the number of nodes of the input graph, and m the number of edges of the input graph. We show that in the worst case a total of \Omega\Gamma \Delta min(m;pn)) bits need to be transmitted in order to solve the MST problem, where is the number of bits required to represent a single edge weight. This implies that if each message contains bits, any BSP algorithm for finding an MST requires communication time\Omega\Gamma g \Delta min(m=p; n)), where g is the gap parameter of the BSP model. In addition, we present two algorithms whose running times match the lower bounds in different situations. Both algorith..