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)(log
n-log
k)/
n when
k =
o(
n) and
n
.
Mathematics Subject Classification (2000): 05C80 - 60C05 - 68R10
* Research supported in part by NSF grant DSM9971788
Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.