Abstract | ||
---|---|---|
We study the expected value of the length L-n of the minimum spanning tree of the complete graph K-n when each edge e is given an independent uniform [0, 1] edge weight. We sharpen the result of Frieze [6] that lim(n ->infinity) E(L-n) = zeta(3) and show that E(L-n) = zeta(3) + c(1)/n + c(2) + o(1)/n4/3, where c(1), c(2) are explicitly defined constants. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1017/S0963548315000024 | COMBINATORICS PROBABILITY & COMPUTING |
Field | DocType | Volume |
Complete graph,Discrete mathematics,Combinatorics,Expected value,Random minimum spanning tree,Mathematics,Frieze,Minimum spanning tree | Journal | 25 |
Issue | ISSN | Citations |
SP1 | 0963-5483 | 4 |
PageRank | References | Authors |
0.49 | 14 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Colin Cooper | 1 | 857 | 91.88 |
Alan M. Frieze | 2 | 4837 | 787.00 |
Nate Ince | 3 | 4 | 0.49 |
Svante Janson | 4 | 1009 | 149.67 |
Joel H. Spencer | 5 | 200 | 54.20 |