  The minimum degree spanning tree (MDST) problem requires the construction of
a spanning tree $T$ for graph $G=(V,E)$ with $n$ vertices, such that the
maximum degree $d$ of $T$ is the smallest among all spanning trees of $G$. In
this paper, we present two new distributed approximation algorithms for the
MDST problem. Our first result is a randomized distributed algorithm that
constructs a spanning tree of maximum degree $\hat d = O(d\log{n})$. It
requires $O((D + \sqrt{n}) \log^2 n)$ rounds (w.h.p.), where $D$ is the graph
diameter, which matches (within log factors) the optimal round complexity for
the related minimum spanning tree problem. Our second result refines this
approximation factor by constructing a tree with maximum degree $\hat d = O(d +
\log{n})$, though at the cost of additional polylogarithmic factors in the
round complexity. Although efficient approximation algorithms for the MDST
problem have been known in the sequential setting since the 1990's, our results
are first efficient distributed solutions for this problem.
