On finding a minimum spanning tree in a network with random weights
✍ Scribed by Colin McDiarmid; Theodore Johnson; Harold S. Stone
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 221 KB
- Volume
- 10
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
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 e is added to the current tree, where k s o d , the probability that this edge e is k k
Ž . incident to the node that was most recently added to the tree equals q qo 1 as dªϱ.
2k
Ž . We also find for example that, if the edge weights are uniformly distributed on 0, 1 , then 1 1 Ž . Ž . the expected value of w e is asymptotic to q rd.