Edge flows in the complete random-lengths network

DOI10.1002/RSA.20306MaRDI QIDQ3055894zbMATH OpenOpenAlexFDO

Authors David Aldous, Shankar Bhamidi

Publication date 10 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0708.0555, https://escholarship.org/uc/item/8c95x2h0

zbMATH Keywords

flowpercolation treerandom graphrandom network

Mathematics Subject Classification ID

Flows in graphs (05C21) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Consider the complete n-vertex graph whose edge-lengths are independent exponentially distributed random variables. Simultaneously for each pair of vertices, put a constant flow between them along the shortest path. Each edge gets some random total flow. In the $noinfty$ limit we find explicitly the empirical distribution of these edge-flows, suitably normalized.

Recommendations

• scientific article; zbMATH DE number 3968280
• Uniform multicommodity flow through the complete graph with random edge-capacities
• Successive shortest paths in complete graphs with random edge weights
• Joint distribution of distances in large random regular networks
• scientific article; zbMATH DE number 3846542

Cites work

• A proof of Parisi's conjecture on the random assignment problem
• Asymptotic fringe distributions for general families of random trees
• First passage percolation on locally treelike networks. I. Dense random graphs
• First-passage percolation on the square lattice
• scientific article; zbMATH DE number 1866312 (Why is no real title available?)
• On the value of a random minimum spanning tree problem
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Percolation–like scaling exponents for minimal paths and trees in the stochastic mean field model
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• Random assignment and shortest path problems
• Scaling and universality in continuous length combinatorial optimization
• Statistical mechanics of complex networks
• The cavity method at zero temperature
• The flooding time in random graphs
• The Structure and Function of Complex Networks
• Universality for the distance in finite variance random graphs

Cited in

(12)

• Uniform multicommodity flow through the complete graph with random edge-capacities
• On the length of the shortest path in a sparse Barak-Erdős graph
• A conversation with David J. Aldous
• Joint distribution of distances in large random regular networks
• Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks
• Distribution of minimal path lengths when edge lengths are independent heterogeneous exponential random variables
• scientific article; zbMATH DE number 3968280 (Why is no real title available?)
• The phases of large networks with edge and triangle constraints
• Preservation of log-concavity under convolution
• Return to the Poissonian city
• Diameter of the stochastic mean-field model of distance
• Uniform multicommodity flows in the hypercube with random edge‐capacities

This page was built for publication: Edge flows in the complete random-lengths network

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