Premium
Edge flows in the complete random‐lengths network
Author(s) -
Aldous David J.,
Bhamidi Shankar
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20306
Subject(s) - random graph , mathematics , vertex (graph theory) , combinatorics , enhanced data rates for gsm evolution , struct , random variable , path (computing) , shortest path problem , flow (mathematics) , limit (mathematics) , constant (computer programming) , path length , graph , discrete mathematics , computer science , geometry , mathematical analysis , statistics , telecommunications , programming language , computer network
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 n → ∞ limit we find explicitly the empirical distribution of these edge‐flows, suitably normalized. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010