On the Length of a Random Minimum Spanning Tree
On the Length of a Random Minimum Spanning Tree
复制标题
关于随机最小生成树的长度
DOI：
10.1017/s0963548315000024
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
J. Spencer
中科院分区：
文献类型：
--
作者：
C. Cooper;A. Frieze;Nate Ince;S. Janson;J. Spencer
我们研究当每条边e被赋予独立的均匀[0, 1]边权重时，完全图Kn的最小生成树的长度Ln的期望值。我们锐化 Frieze [6] 的结果 limn→∞$\mathbb{E}$(Ln) = ze(3) 并表明 $$
\mathbb{E}(L_n)=\zeta(3)+\frac{c_1}{n}+\frac{c_2+o(1)}{n^{4/3}},
$$ 其中 c1、c2 是显式定义的常量。
We study the expected value of the length Ln of the minimum spanning tree of the complete graph Kn when each edge e is given an independent uniform [0, 1] edge weight. We sharpen the result of Frieze [6] that limn→∞$\mathbb{E}$(Ln) = ζ(3) and show that $$
\mathbb{E}(L_n)=\zeta(3)+\frac{c_1}{n}+\frac{c_2+o(1)}{n^{4/3}},
$$ where c1, c2 are explicitly defined constants.