David Gamarnik
SODA 2004
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 → ∞.
David Gamarnik
SODA 2004
Don Coppersmith, David Gamarnik, et al.
SODA 1998
Richard Arratia, Béla Bollobás, et al.
Journal of Combinatorial Theory. Series B
Richard Arratia, Béla Bollobás, et al.
Combinatorica