Abstract
The weight of a randomly chosen link in the shortest path tree on the complete graph with exponential i.i.d. link weights is studied. The corresponding exact probability generating function and the asymptotic law are derived. As a remarkable coincidence, this asymptotic law is precisely the same as the distribution of the cost of one job in the random assignment problem. We also show that the asymptotic (scaled) maximum interattachment time to that shortest path tree, which is a uniform recursive tree, equals the square of the Dedekind Eta function, a central function in modular forms, elliptic functions, and the theory of partitions.
Original language | English |
---|---|
Title of host publication | Random Structures and Algorithms |
Editors | s.n. |
Place of Publication | s.l. |
Publisher | Wiley |
Pages | - |
Number of pages | 30 |
DOIs | |
Publication status | Published - 2010 |
Keywords
- edited works: contributions
- Boekdeel internat.wet