The longest minimum-weight path in a complete graph

DOI10.1017/S0963548309990204MaRDI QIDQ3557522zbMATH OpenOpenAlexFDO

Authors Louigi Addario-Berry, Nicolas Broutin, Gábor Lugosi

Publication date 23 April 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.0275

zbMATH Keywords

minimum weight path

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Abstract: 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 alpha^* log n$edgeswherealph{a}^{\ast }3.5911istheuniquesolutionoftheequation$alpha log(alpha) - alpha =1. This answers a question posed by Janson (1999).

Recommendations

• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• The weight of the shortest path tree
• Weak disorder in the stochastic mean-field model of distance. II
• Successive shortest paths in complete graphs with random edge weights
• On Shortest Paths in Graphs with Random Weights

Cites work

• A Remark on Stirling's Formula
• Branching processes in the analysis of the heights of trees
• Correlation inequalities on some partially ordered sets
• Note on the heights of random recursive trees and random m‐ary search trees
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Percolation
• Size and Weight of Shortest Path Trees with Exponential Link Weights
• The Weight and Hopcount of the Shortest Path in the Complete Graph with Exponential Weights
• The weight of the shortest path tree

Cited in

(14)

• The expected length of a shortest path
• First passage percolation on random graphs with finite mean degrees
• Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics
• Finding the Minimum-Weight k-Path
• Weight of a link in a shortest path tree and the Dedekind eta function
• Shortest-weight paths in random regular graphs
• The weight of the shortest path tree
• The Weight and Hopcount of the Shortest Path in the Complete Graph with Exponential Weights
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Diameter of the stochastic mean-field model of distance
• Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
• Long-range first-passage percolation on the torus
• Increasing paths in random temporal graphs
• Percolation of averages in the stochastic mean field model: the near-supercritical regime

This page was built for publication: The longest minimum-weight path in a complete graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557522)