Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-11T15:22:01.207Z Has data issue: false hasContentIssue false
  • English
  • Français

On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph

Part of: Graph theory

Published online by Cambridge University Press:  09 October 2017

ALAN FRIEZE  and
TONY JOHANSSON
ALAN FRIEZE
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: alan@random.math.cmu.edu)
TONY JOHANSSON
Affiliation:
Department of Mathematics, Uppsala University, 751 06 Uppsala, Sweden (e-mail: tony.johanssson@math.uu.se)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Assume that the edges of the complete graph Kn are given independent uniform [0, 1] weights. We consider the expected minimum total weight μk of k ⩽ 2 edge-disjoint spanning trees. When k is large we show that μk ≈ k2. Most of the paper is concerned with the case k = 2. We show that m2 tends to an explicitly defined constant and that μ2 ≈ 4.1704288. . . .

MSC classification

Primary: 05C80: Random graphs
Secondary: 05C22: Signed and weighted graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 2 , March 2018 , pp. 228 - 244
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Aldous, D. (1992) Asymptotics in the random assignment problem. Probab. Theory Rel. Fields 93 507–534.CrossRefGoogle Scholar
[2] Aldous, D. (2001) The ζ(2) limit in the random assignment problem. Random Struct. Alg. 4 381–418.CrossRefGoogle Scholar
[3] Avram, F. and Bertsimas, D. (1992) The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach. Ann. Appl. Probab. 2 113–130.CrossRefGoogle Scholar
[4] Beveridge, A., Frieze, A. M. and McDiarmid, C. J. H. (1998) Minimum length spanning trees in regular graphs. Combinatorica 18 311–333.Google Scholar
[5] Bollobás, B. (1980) A probabilistic proof of an asymptotic formula for the number of labelled graphs. Europ. J. Combin. 1 311–316.CrossRefGoogle Scholar
[6] Cain, J. A., Sanders, P. and Wormald, N. (2007) The random graph threshold for k-orientability and a fast algorithm for optimal multiple-choice allocation. In SODA 2007: Proc. 18th Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, pp. 469–476.Google Scholar
[7] Cooper, C., Frieze, A. M., Ince, N., Janson, S. and Spencer, J. (2016) On the length of a random minimum spanning tree. Combin. Probab. Comput. 25, 89–107.CrossRefGoogle Scholar
[8] Durrett, R. (1991) Probability: Theory and Examples, Wadsworth & Brooks/Cole.Google Scholar
[9] Fenner, T. I. and Frieze, A. M. (1982) On the connectivity of random m-orientable graphs and digraphs. Combinatorica 2 347–359.Google Scholar
[10] Frieze, A. M. (1985) On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10 47–56.Google Scholar
[11] Frieze, A. M. (1986) On large matchings and cycles in sparse random graphs. Discrete Math. 59 243–256.CrossRefGoogle Scholar
[12] Frieze, A. M. (2004) On random symmetric travelling salesman problems. Math. Oper. Res. 29 878–890.CrossRefGoogle Scholar
[13] Frieze, A. M. and Grimmett, G. R. (1985) The shortest path problem for graphs with random arc-lengths. Discrete Appl. Math. 10 57–77.CrossRefGoogle Scholar
[14] Frieze, A. M. and McDiarmid, C. J. H. (1989) On random minimum length spanning trees. Combinatorica 9 363–374.Google Scholar
[15] Frieze, A. M., Ruszinko, M. and Thoma, L. (2000) A note on random minimum length spanning trees. Electron. J. Combin. 7 R41.CrossRefGoogle Scholar
[16] Gao, P., Pérez-Giménez, X. and Sato, C. M. (2014) Arboricity and spanning-tree packing in random graphs with an application to load balancing. Extended abstract published in SODA 2014, pp. 317–326.Google Scholar
[17] Janson, S. (1995) The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph. Random Struct. Alg. 7 337–355.Google Scholar
[18] Janson, S. (1999) One, two and three times log n/n for paths in a complete graph with random weights. Combin. Probab. Comput. 8 347–361.CrossRefGoogle Scholar
[19] Janson, S. and Łuczak, M. J. (2007) A simple solution to the k-core problem. Random Struct. Alg. 30 50–62.Google Scholar
[20] Karp, R. M. (1979) A patching algorithm for the non-symmetric traveling salesman problem. SIAM J. Comput. 8 561–573.CrossRefGoogle Scholar
[21] Kordecki, W. and Lyczkowska-Hanćkowiak, A. (2013) Exact expectation and variance of minimal basis of random matroids. Discussiones Mathematicae Graph Theory 33 277–288.Google Scholar
[22] Linusson, S. and Wästlund, J. (2004) A proof of Parisi's conjecture on the random assignment problem. Probab. Theory Rel. Fields 128 419–440.CrossRefGoogle Scholar
[23] Łuczak, T. (1991) Size and connectivity of the k-core of a random graph. Discrete Math. 91 61–68.CrossRefGoogle Scholar
[24] Nair, C., Prabhakar, B. and Sharma, M. (2005) Proofs of the Parisi and Coppersmith–Sorkin random assignment conjectures. Random Struct. Alg. 27 413–444.CrossRefGoogle Scholar
[25] Nash-Williams, C. St. J. A. (1961) Edge-disjoint spanning trees of finite graphs. J. London Math. Soc. 36 445–450.Google Scholar
[26] Nash-Williams, C. St. J. A. (1964) Decomposition of finite graphs into forests. J. London Math. Soc. 39 12.Google Scholar
[27] Oxley, J. (1992) Matroid Theory, Oxford University Press.Google Scholar
[28] Penrose, M. (1998) Random minimum spanning tree and percolation on the n-cube. Random Struct. Alg. 12 63–82.3.0.CO;2-R>CrossRefGoogle Scholar
[29] Pittel, B., Spencer, J. and Wormald, N. (1996) Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B 67 111–151.CrossRefGoogle Scholar
[30] Steele, J. M. (1987) On Frieze's ζ(3) limit for lengths of minimal spanning trees. Discrete Appl. Math. 18 99–103.Google Scholar
[31] Wästlund, J. (2009) An easy proof of the ζ(2) limit in the random assignment problem. Electron. Comm. Probab. 14 261–269.Google Scholar
[32] Wästlund, J. (2010) The mean field traveling salesman and related problems. Acta Math. 204 91–150.CrossRefGoogle Scholar
[33] Welsh, D. J. A. (1976) Matroid Theory, Academic Press.Google Scholar