Communication-Optimal Parallel Minimum Spanning Tree Algorithms
Micah Adler, Wolfgang Dittrich, Ben Juurlink, Miroslaw Kutylowski
and Ingo Rieping
Juni 1998
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(\kappa \cdot \min(m, pn))$ bits need
to be transmitted in order to solve the MST problem, where $\kappa$ is
the number of bits required to represent a single edge weight. This implies
that if each message contains $\kappa$ bits, any BSP algorithm for finding
an MST requires communication time $\Omega(g \cdot \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 \geq n \cdot \log p$. This
is the first linear work BSP algorithm for finding an MST in sparse graphs.
Full
paper in compressed Postscript format.