Communication-optimal parallel minimum spanning tree algorithms (extended abstract)
Micah Adler, Wolfgang Dittrich, Ben Juurlink, Mirosław Kutyłowski, Ingo Rieping · 1998
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...