Communication-Optimal Parallel
Minimum Spanning Tree Algorithms
Micah Adler, Wolfgang Dittrich,
Ben Juurlink, Miroslaw Kutylowski, Ingo Rieping
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(k min(m,
pn)) bits need to be transmitted in order to solve the MST problem,
where k is the number of bits required to represent a single edge
weight. This implies that if a message can contain at most O(k) bits,
any BSP algorithm for finding an MST requires communication time Omega(g
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 algorithms perform linear
work and use a number of supersteps independent of the input size. The
first algorithm is simple but can employ at most m/n processors
efficiently. Hence, it should be applied in situations where the input
graph is relatively dense. The second algorithm is a randomized
algorithm that performs linear work with high probability, provided that
m =< n log p. This is the first linear work BSP algorithm for finding an
MST in sparse graphs.