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

first passage percolationlaw of large numbersrandom regular graphsshortest pathsweighted random graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) 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)

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

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)