Short paths for first passage percolation on the complete graph
From MaRDI portal
(Redirected from Publication:359585)
Abstract: We study the complete graph equipped with a topology induced by independent and identically distributed edge weights. The focus of our analysis is on the weight W_n and the number of edges H_n of the minimal weight path between two distinct vertices in the weak disorder regime. We establish novel and simple first and second moment methods using path counting to derive first order asymptotics for the considered quantities. Our results are stated in terms of a sequence of parameters (s_n) that quantifies the extreme-value behaviour of the edge weights, and that describes different universality classes for first passage percolation on the complete graph. These classes contain both n-independent and n-dependent edge weight distributions. The method is most effective for the universality class containing the edge weights E^{s_n}, where E is an exponential(1) random variable and s_n log n -> infty, s_n^2 log n -> 0. We discuss two types of examples from this class in detail. In addition, the class where s_n log n stays finite is studied. This article is a contribution to the program initiated in cite{BhaHof12}.
Recommendations
- First passage percolation on random geometric graphs and an application to shortest-path trees
- Construction of a short path in high-dimensional first passage percolation
- First-passage percolation on the random graph
- Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics
- First passage percolation on random graphs with finite mean degrees
- Long paths in first passage percolation on the complete graph II. Global branching dynamics
- First passage percolation on inhomogeneous random graphs
- First passage percolation on the Erdős-Rényi random graph
- Universality for first passage percolation on sparse random graphs
Cites work
- scientific article; zbMATH DE number 3971949 (Why is no real title available?)
- scientific article; zbMATH DE number 486467 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Distances in random graphs with finite mean and infinite variance degrees
- Distances in random graphs with finite variance degrees
- First passage percolation on locally treelike networks. I. Dense random graphs
- First passage percolation on the Erdős-Rényi random graph
- First-passage percolation on the random graph
- One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
- Random graphs and complex networks. Volume 1
- Short paths for first passage percolation on the complete graph
- Universality for first passage percolation on sparse random graphs
- Weak disorder asymptotics in the stochastic mean-field model of distance
- Weak disorder in the stochastic mean-field model of distance. II
Cited in
(10)- One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
- Weak disorder asymptotics in the stochastic mean-field model of distance
- Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics
- Long paths in first passage percolation on the complete graph II. Global branching dynamics
- Long-range first-passage percolation on the torus
- Short paths for first passage percolation on the complete graph
- Successive shortest paths in complete graphs with random edge weights
- Degree distribution of shortest path trees and bias of network sampling algorithms
- Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
- Last passage percolation on the complete graph
This page was built for publication: Short paths for first passage percolation on the complete graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q359585)
