2008/09/01 by Louigi Addario-Berry, Louigi Addario‐Berry, Addario-Berry, Louigi +5
Computer Science · Mathematics · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Privacy-Preserving Technologies in Data #Probability (math.PR) #Random Matrices and Applications #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.0809.0275
21 pages; minor corrections and clarifications
openalex publication_date 2008/09/01 · arxiv created 2009/02/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the minimum-weight path between any pair of nodes of the n-vertex complete graph in which the weights of the edges are i.i.d. exponentially distributed random variables. We show that the longest of these minimum-weight paths has about α^* log n edges where α^* ~ 3.5911 is the unique solution of the equation alpha log(alpha) - α=1. This answers a question posed by Janson (1999).