The longest minimum-weight path in a complete graph

Simple item page
dc.creatorAddario-Berry, Louigi
dc.creatorBroutin, Nicolas
dc.creatorLugosi, Gabor
dc.date2008-09-01
dc.date2009-02-06
dc.date.accessioned2026-07-07T12:38:05Z
dc.date.available2026-07-07T12:38:05Z
dc.descriptionWe 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).
dc.description21 pages; minor corrections and clarifications
dc.identifierhttps://arxiv.org/abs/0809.0275
dc.identifierhttp://arxiv.org/abs/0809.0275
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/218631
dc.subjectCombinatorics
dc.subjectProbability
dc.titleThe longest minimum-weight path in a complete graph
dc.typetext

Files

Collections

arXiv