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.
By: Bela Bollobas, David P. Gamarnik, Oliver Riordan, Benny Sudakov
Published in: Combinatorica , volume 24, (no 2), pages 187-207 in 2004
Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.
Questions about this service can be mailed to reports@us.ibm.com .