Shortest-weight paths in random regular graphs

DOI10.1137/120899534MaRDI QIDQ3192154zbMATH OpenOpenAlexFDO

Authors Hamed Amini, Yuval Peres

Publication date 26 September 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathsfirst passage percolationlaw of large numbersrandom regular graphsweighted random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Stochastic network models in operations research (90B15)

Abstract: Consider a random regular graph with degree $d$ and of size $n$. Assign to each edge an i.i.d. exponential random variable with mean one. In this paper we establish a precise asymptotic expression for the maximum number of edges on the shortest-weight paths between a fixed vertex and all the other vertices, as well as between any pair of vertices. Namely, for any fixed $dgeq3$, we show that the longest of these shortest-weight paths has about $hatalphalogn$ edges where $hatalpha$ is the unique solution of the equation $alphalog(fracd-2d-1alpha)-alpha=fracd-3d-2$, for $alpha>fracd-1d-2$.

Recommendations

• On Shortest Paths in Graphs with Random Weights
• The longest minimum-weight path in a complete graph
• The diameter of weighted random graphs
• Weak disorder in the stochastic mean-field model of distance. II
• The weight of the shortest path tree

Cited in

(10)

• Successive shortest paths in complete graphs with random edge weights
• Diameter of the stochastic mean-field model of distance
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• The diameter of weighted random graphs
• The shortest-path problem for graphs with random arc-lengths
• The Distribution of Path Lengths On Directed Weighted Graphs
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• On Shortest Paths in Graphs with Random Weights
• Joint distribution of distances in large random regular networks

This page was built for publication: Shortest-weight paths in random regular graphs

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