The longest minimum-weight path in a complete graph

Abstract

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$edgeswhere{\alpha }^{\ast }3.5911istheuniquesolutionoftheequation$alpha log(alpha) - α=1. This answers a question posed by Janson (1999).

21 pages; minor corrections and clarifications