  In the complete graph on n vertices, when each edge has a weight which is an
exponential random variable, Frieze proved that the minimum spanning tree has
weight tending to zeta(3)=1/1^3+1/2^3+1/3^3+... as n goes to infinity. We
consider spanning trees constrained to have depth bounded by k from a specified
root. We prove that if k > log_2 log n+omega(1), where omega(1) is any function
going to infinity with n, then the minimum bounded-depth spanning tree still
has weight tending to zeta(3) as n -> infinity, and that if k < log_2 log n,
then the weight is doubly-exponentially large in log_2 log n - k. It is NP-hard
to find the minimum bounded-depth spanning tree, but when k < log_2 log n -
omega(1), a simple greedy algorithm is asymptotically optimal, and when k >
log_2 log n+omega(1), an algorithm which makes small changes to the minimum
(unbounded depth) spanning tree is asymptotically optimal. We prove similar
results for minimum bounded-depth Steiner trees, where the tree must connect a
specified set of m vertices, and may or may not include other vertices. In
particular, when m = const * n, if k > log_2 log n+omega(1), the minimum
bounded-depth Steiner tree on the complete graph has asymptotically the same
weight as the minimum Steiner tree, and if 1 <= k <= log_2 log n-omega(1), the
weight tends to (1-2^{-k}) sqrt{8m/n} [sqrt{2mn}/2^k]^{1/(2^k-1)} in both
expectation and probability. The same results hold for minimum bounded-diameter
Steiner trees when the diameter bound is 2k; when the diameter bound is
increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a
factor of 2^{1/(2^k-1)}.
