First Passage Percolation on the Erdős–Rényi Random Graph

DOI10.1017/S096354831100023XzbMath1238.60092arXiv1005.4104OpenAlexW2100172709MaRDI QIDQ3103620

Shankar Bhamidi, Remco van der Hofstad, Gerard Hooghiemstra

Publication date: 8 December 2011

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

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

zbMATH Keywords

branching processrandom graphrandom treesPercolationweighted paths

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items (22)

First passage percolation on the Newman-Watts small world model ⋮ Local neighbourhoods for first-passage percolation on the configuration model ⋮ A functional central limit theorem for SI processes on configuration model graphs ⋮ Short paths for first passage percolation on the complete graph ⋮ Probabilistic analysis of optimization problems on generalized random shortest path metrics ⋮ Information Spreading in a Large Population of Active Transmitters and Passive Receivers ⋮ Geometric aspects of functional analysis. Proceedings of the Israel seminar (GAFA) 2011--2013 ⋮ Long paths in first passage percolation on the complete graph II. Global branching dynamics ⋮ Maximal Steiner Trees in the Stochastic Mean-Field Model of Distance ⋮ Tight fluctuations of weight-distances in random graphs with infinite-variance degrees ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ Weighted distances in scale-free configuration models ⋮ Epidemics and vaccination on weighted graphs ⋮ Speeding up non-Markovian first-passage percolation with a few extra edges ⋮ Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs ⋮ Successive shortest paths in complete graphs with random edge weights ⋮ Competing first passage percolation on random regular graphs ⋮ The front of the epidemic spread and first passage percolation ⋮ Joint Distribution of Distances in Large Random Regular Networks ⋮ First Passage Percolation on Inhomogeneous Random Graphs ⋮ The diameter of weighted random graphs ⋮ Degree distribution of shortest path trees and bias of network sampling algorithms

Cites Work

• First passage percolation on random graphs with finite mean degrees
• FIRST-PASSAGE PERCOLATION ON THE RANDOM GRAPH
• First passage percolation on locally treelike networks. I. Dense random graphs
• On tree census and the giant component in sparse random graphs
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Real Analysis and Probability
• The diameter of sparse random graphs

This page was built for publication: First Passage Percolation on the Erdős–Rényi Random Graph