One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights

SVANTE JANSON

doi:10.1017/S0963548399003892

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.

Consider the minimal weights of paths between two points in a complete graph Kn with random weights on the edges, the weights being, for instance, uniformly distributed. It is shown that, asymptotically, this is log n/n for two given points, that the maximum if one point is fixed and the other varies is 2 log n/n, and that the maximum over all pairs of points is 3 log n/n.

Some further related results are given as well, including results on asymptotic distributions and moments, and on the number of edges in the minimal weight paths.

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Howard, C. Douglas 2004. Probability on Discrete Structures. Vol. 110, Issue. , p. 125.

Aldous, David J. 2005. Percolation–like scaling exponents for minimal paths and trees in the stochastic mean field model. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, Vol. 461, Issue. 2055, p. 825.

Nair, Chandra Prabhakar, Balaji and Sharma, Mayank 2005. Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures. Random Structures & Algorithms, Vol. 27, Issue. 4, p. 413.

Barbour, Andrew and Reinert, Gesine 2006. Discrete small world networks. Electronic Journal of Probability, Vol. 11, Issue. none,

Ben-Naim, E Hastings, M B and Izraelevitz, D 2007. Statistics of partial minima. Journal of Physics A: Mathematical and Theoretical, Vol. 40, Issue. 47, p. F1021.

HOOGHIEMSTRA, GERARD and VAN MIEGHEM, PIET 2008. The Weight and Hopcount of the Shortest Path in the Complete Graph with Exponential Weights. Combinatorics, Probability and Computing, Vol. 17, Issue. 4, p. 537.

Bhamidi, Shankar 2008. First passage percolation on locally treelike networks. I. Dense random graphs. Journal of Mathematical Physics, Vol. 49, Issue. 12,

Chebolu, Prasad Frieze, Alan Melsted, Páll and Sorkin, Gregory B. 2009. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Vol. 5687, Issue. , p. 434.

Aldous, David J. and Bhamidi, Shankar 2010. Edge flows in the complete random‐lengths network. Random Structures & Algorithms, Vol. 37, Issue. 3, p. 271.

ADDARIO-BERRY, LOUIGI BROUTIN, NICOLAS and LUGOSI, GÁBOR 2010. The Longest Minimum-Weight Path in a Complete Graph. Combinatorics, Probability and Computing, Vol. 19, Issue. 1, p. 1.

Bhamidi, Shankar van der Hofstad, Remco and Hooghiemstra, Gerard 2010. Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks. Advances in Applied Probability, Vol. 42, Issue. 3, p. 706.

Bhamidi, Shankar van der Hofstad, Remco and Hooghiemstra, Gerard 2010. First passage percolation on random graphs with finite mean degrees. The Annals of Applied Probability, Vol. 20, Issue. 5,

Van Mieghem, Piet 2010. Weight of a link in a shortest path tree and the Dedekind Eta function. Random Structures & Algorithms, Vol. 36, Issue. 3, p. 341.

Peres, Yuval Sotnikov, Dmitry Sudakov, Benny and Zwick, Uri 2010. All-Pairs Shortest Paths in O(n²) Time with High Probability. p. 663.

Abdullah, Mohammed Cooper, Colin and Draief, Moez 2011. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Vol. 6845, Issue. , p. 351.

BHAMIDI, SHANKAR VAN DER HOFSTAD, REMCO and HOOGHIEMSTRA, GERARD 2011. First Passage Percolation on the Erdős–Rényi Random Graph. Combinatorics, Probability and Computing, Vol. 20, Issue. 5, p. 683.

Ross, Sheldon M. 2012. Distribution of Minimal Path Lengths when Edge Lengths are Independent Heterogeneous Exponential Random Variables. Journal of Applied Probability, Vol. 49, Issue. 3, p. 895.

Doerr, Benjamin Fouz, Mahmoud and Friedrich, Tobias 2012. Algorithm Theory – SWAT 2012. Vol. 7357, Issue. , p. 307.

Angel, Omer Flaxman, Abraham D. and Wilson, David B. 2012. A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks. Combinatorica, Vol. 32, Issue. 1, p. 1.

Download full list

Article contents

One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights

Abstract

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests