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

作者：Angel Omer^*; Flaxman Abraham D; Wilson David B

来源：Combinatorica, 2012, 32(1): 1-33.

DOI：10.1007/s00493-012-2552-z

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) +aEuro broken vertical bar as n -> a. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k a parts per thousand yen log(2) logn+omega(1), where omega(1) is any function going to a with n, then the minimum bounded-depth spanning tree still has weight tending to zeta(3) as n -> a, and that if k < log(2) logn, then the weight is doubly-exponentially large in log(2) logn - k. It is NP-hard to find the minimum bounded-depth spanning tree, but when ka parts per thousand currency signlog(2) logn-omega(1), a simple greedy algorithm is asymptotically optimal, and when k a parts per thousand yen log(2) logn+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=constxn, if ka parts per thousand yenlog(2) logn+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 a parts per thousand currency sign k a parts per thousand currency sign log(2) logn-omega(1), the weight tends to 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 .

• 出版日期2012-1