Richard Arratia, Béla Bollobás, et al.
Combinatorica
Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1 + o(1))(k - 1)(logn - log k)/n when k = o(n) and n → ∞.
Richard Arratia, Béla Bollobás, et al.
Combinatorica
David Gamarnik, Mark S. Squillante
Stochastic Models
David Gamarnik, Dmitriy Katz
Annals of Applied Probability
David Gamarnik, Tomasz Nowicki, et al.
Ergodic Theory and Dynamical Systems