Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T15:18:25.629Z Has data issue: false hasContentIssue false
  • English
  • Français

The Longest Minimum-Weight Path in a Complete Graph

Published online by Cambridge University Press:  22 June 2009

LOUIGI ADDARIO-BERRY ,
NICOLAS BROUTIN  and
GÁBOR LUGOSI
LOUIGI ADDARIO-BERRY
Affiliation:
Département de Mathématiques et de Statistique, Université de Montréal, CP 6128, Succ. Centre-ville, Montreal, Quebec, H3C 3J7, Canada (e-mail: louigi@gmail.com)
NICOLAS BROUTIN
Affiliation:
Projet Algorithms, INRIA Rocquencourt, 78153 Le Chesnay, France (e-mail: nicolas.broutin@m4x.org)
GÁBOR LUGOSI
Affiliation:
Department of Economics, Pompeu Fabra University, Ramon Trias Fargas 25-27, 08005, Barcelona, Spain (e-mail: lugosi@upf.es)
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.

We consider the minimum-weight path between any pair of nodes of the n-vertex complete graph in which the weights of the edges are i.i.d. exponentially distributed random variables. We show that the longest of these minimum-weight paths has about α* log n edges, where α* ≈ 3.5911 is the unique solution of the equation α log α − α = 1. This answers a question posed by Janson [8].

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 1 , January 2010 , pp. 1 - 19
Copyright
Copyright © Cambridge University Press 2009

References

[1]Alon, N. and Spencer, J. (2000) The Probabilistic Method, 2nd edn, Wiley, New York.CrossRefGoogle Scholar
[2]Dembo, A. and Zeitouni, O. (1998) Large Deviation Techniques and Applications, 2nd edn, Springer.CrossRefGoogle Scholar
[3]Devroye, L. (1987) Branching processes in the analysis of the heights of trees. Acta Informatica 24 277–298.CrossRefGoogle Scholar
[4]Fortuin, C. M., Kasteleyn, P. W. and Ginibre, J. (1971) Correlational inequalities for partially ordered sets. Comm. Math. Phys. 22 89–103.Google Scholar
[5]Grimmett, G. R. (1999) Percolation, Vol. 321 of A Series of Comprehensive Studies in Mathematics, 2nd edn, Springer.CrossRefGoogle Scholar
[6]Harris, T. E. (1960) A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc. 56 13–20.CrossRefGoogle Scholar
[7]Hooghiemstra, G. and Van Mieghem, P. (2008) The weight and hopcount of the shortest path in the complete graph with exponential weights. Combin. Probab. Comput. 17 537–548.Google Scholar
[8]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.Google Scholar
[9]Pittel, B. (1994) Note on the height of recursive trees and m-ary search trees. Random Struct. Alg. 5 337–347.Google Scholar
[10]Robbins, H. (1955) A remark on Stirling's formula. Amer. Math. Monthly 62 26–29.Google Scholar
[11]Rogers, L. C. G. and Williams, D. (2000) Diffusions, Markov Processes, and Martingales, Vol. 1, Cambridge University Press.Google Scholar
[12]Shorack, G. R. and Wellner, J. A. (1986) Empirical Processes with Applications to Statistics, Wiley.Google Scholar
[13]Smythe, R. T. and Mahmoud, H. M. (1995) A survey of recursive trees. Theoret. Probab. Math. Statist. 51 1–27.Google Scholar
[14]vander Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2006) Size and weight of shortest path trees with exponential link weights. Combin. Probab. Comput. 15 903–926.Google Scholar
[15]van der Hofstad, R., Hooghiemstra, G. and VanMieghem, P. Mieghem, P. (2007) The weight of the shortest path tree. Random Struct. Alg. 30 359–379.Google Scholar