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.