The Longest Minimum-Weight Path in a Complete Graph
From MaRDI portal
Publication:3557522
DOI10.1017/S0963548309990204zbMath1209.05219arXiv0809.0275MaRDI QIDQ3557522
Gábor Lugosi, Louigi Addario-Berry, Nicolas Broutin
Publication date: 23 April 2010
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0809.0275
05C80: Random graphs (graph-theoretic aspects)
05C38: Paths and cycles
05C22: Signed and weighted graphs
Related Items
Random shortest paths: non-Euclidean instances for metric optimization problems, First passage percolation on random graphs with finite mean degrees
Cites Work
- Branching processes in the analysis of the heights of trees
- Correlation inequalities on some partially ordered sets
- A Remark on Stirling's Formula
- Size and Weight of Shortest Path Trees with Exponential Link Weights
- The weight of the shortest path tree
- The Weight and Hopcount of the Shortest Path in the Complete Graph with Exponential Weights
- Percolation
- Note on the heights of random recursive trees and random m‐ary search trees
- One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights