A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

Details A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

2008-10-27

arxiv.org/abs/0810.4908v2

Mathematics

Probability

30 pages, v2 has minor revisions

Scientific paper

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)}.

Affiliated with

Also associated with

No associations

Rating

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-324757