On the value of a random minimum weight steiner tree

被引：14

作者：

Bollobás, B ^{[1
]}

Gamarnik, D

Riordan, O

Sudakov, B

机构：

[1] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA

[2] Univ Cambridge Trinity Coll, Cambridge CB2 1TQ, England

[3] IBM Corp, Thomas J Watson Res Ctr, Yorktown Hts, NY 10598 USA

来源：

COMBINATORICA | 2004年 / 24卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1007/s00493-004-0013-z

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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-->infinity.

引用

页码：187 / 207

页数：21

共 18 条

[1] The ζ(2) limit in the random assignment problem [J].