The longest minimum-weight path in a complete graph

Addario-Berry, Louigi; Broutin, Nicolas; Lugosi, Gabor

The longest minimum-weight path in a complete graph

Authors

Addario-Berry, Louigi

Broutin, Nicolas

Lugosi, Gabor

Description

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).
21 pages; minor corrections and clarifications