On finding a minimum spanning tree in a network with random weights
Colin McDiarmid, Theodore Johnson, Harold Samuel Stone · Random Structures and Algorithms · 1997
We investigate Prim's standard “tree-growing” method for finding a minimum spanning tree, when applied to a network in which all degrees are about d and the edges e have independent identically distributed random weights w(e). We find that when the kth edge ek is added to the current tree, where k=o(\sqrt{d}), the probability that this edge ek is incident to the node that was most recently added to the tree equals {1\over 2}+{1\over 2k}+o(1) as d→∞. We also find for example that, if the edge weights are uniformly distributed on (0, 1), then the expected value of w(ek) is asymptotic to ({1\over 2}+{1\over 2k})/d. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 187–204 (1997)