×

On Frieze’s \(\zeta\) (3) limit for lengths of minimal spanning trees. (English) Zbl 0621.05012

The length of the minimal spanning tree on the complete graph on n vertices with edge weights determined by independent non-negative random variables with distribution F is proved to converge in probability to \(\zeta\) (3)/F’(0), provided only that F have a nonzero derivative at the origin. In particular, no other smoothness or moment conditions are placed on F. This augments the result of Frieze for random variables with finite variances and differentiable distribution.

MSC:

05C05 Trees
05C35 Extremal problems in graph theory
05C80 Random graphs (graph-theoretic aspects)
60K05 Renewal theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., Data Structures and Algorithms (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0307.68053
[2] Erdös, P.; Rényi, A., (Turán, P., Selected Papers of Alfréd Rényi, 2 (1960), Akadémiai Kaido: Akadémiai Kaido Budapest), 482-525
[3] Fenner, T. I.; Frieze, A. M., On tkhe connectivity of random \(m- orientable\) graphs and digraphs, Combinatorica, 2, 347-359 (1982) · Zbl 0523.05056
[4] Frieze, A. M., On the value of a minimal spanning tree problem (1982), Queen Mary College: Queen Mary College London, Technical Report
[5] Frieze, A. M., On the value of a minimal spanning tree problem, Discrete Appl. Math., 10, 47-56 (1985) · Zbl 0578.05015
[6] Karp, R. M.; Steele, J. M., Probabilistic analysis of heuristics, (Lawler, E. L.; etal., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985), Wiley-Interscience: Wiley-Interscience New York), 181-206 · Zbl 0582.90100
[7] Knuth, D. E.; Schönhage, A., The expected linearity of a simple equivalence algorithm, Theoret. Comput. Sc., 6, 281-315 (1978) · Zbl 0377.68024
[8] Lueker, G. S., Optimization problems on graphs with independent random edge weights, SIAM J. Comput., 10, 338-351 (1981) · Zbl 0461.05059
[9] D.W. Walkup, On the expected value of a random assignment problem, SIAM J. Comput. 8 440-442.; D.W. Walkup, On the expected value of a random assignment problem, SIAM J. Comput. 8 440-442. · Zbl 0413.68062
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.