×

On finding a minimum spanning tree in a network with random weights. (English) Zbl 0872.60008

Summary: 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 \(k\)th edge \(e_k\) is added to the current tree, where \(k=o (\sqrt d)\), the probability that this edge \(e_k\) is incident to the node that was most recently added to the tree equals \({1 \over 2} +{1\over 2k} +o(1)\) as \(d\to\infty\). We also find for example that, if the edge weights are uniformly distributed on (0,1), then the expected value of \(w(e_k)\) is asymptotic to \(({1\over 2} +{1 \over 2k})/d\).

MSC:

60C05 Combinatorial probability
05C05 Trees
60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, Network Flows (1993)
[2] Aldous, A random tree model associated with random graphs, Random Struct. Alg. 1 pp 383– (1990) · Zbl 0747.05077
[3] Aldous, The continuum random tree I, Ann. Probab. 19 pp 1– (1991) · Zbl 0722.60013
[4] Aldous, Asymptotic fringe distributions for general families of random trees, Ann. Appl. Probab. 1 pp 228– (1991) · Zbl 0733.60016
[5] Alonso, Random Generation of Trees (1995) · doi:10.1007/978-1-4757-6353-9
[6] Avram, The minimum spanning tree constant in geometric probability and under the independent model: a unified approach, Ann. Appl. Probab. 2 pp 113– (1992) · Zbl 0755.60011
[7] Balińska, Random recursive forests, Random Struct. Alg. 5 pp 3– (1994) · Zbl 0792.60007
[8] Brassard, Algorithmics (1988)
[9] Devroye, The strong convergence of maximal degrees in uniform random recursive trees and dags, Random Struct. Alg. 7 pp 1– (1995)
[10] Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 pp 269– (1959) · Zbl 0092.16002
[11] Frieze, On the value of a random minimum spanning tree problem, Discrete Appl. Math. 10 pp 47– (1985) · Zbl 0578.05015
[12] Frieze, On random minimum length spanning trees, Combinatorica 9 pp 363– (1989) · Zbl 0712.05050
[13] Graham, Concrete Mathematics (1989)
[14] Janson, The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph, Random Struct. Alg. 7 pp 337– (1995) · Zbl 0844.05085
[15] Jarńik, O jistém problemu minimálnim, Acta Soc. Sci. Natur. Morauicae 6 pp 57– (1930)
[16] Łuczak, Components of random forests, Combinat. Probab. Comput. 1 pp 35– (1992) · Zbl 0793.05109 · doi:10.1017/S0963548300000067
[17] Mahmoud, Evolution of Random Search Trees (1992) · Zbl 0762.68033
[18] McDiarmid, London Mathematical Society Lecture Note Series 141, in: Surveys in Combinatorics pp 148– (1989)
[19] Papadimitriou, Combinatorial Optimization (1982)
[20] Pittel, Note on the heights of random recursive trees and random m-ary search trees, Random Struct. Alg. 5 pp 337– (1994) · Zbl 0790.05077
[21] Prim, Shortest connection networks and some generalizations, Bell Syst. Tech. J. 36 pp 1389– (1957) · doi:10.1002/j.1538-7305.1957.tb01515.x
[22] Timofeev, On finding the expected length of a random minimal tree, Theor. Probab. Appl. 32 pp 361– (1987) · Zbl 0672.60017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.