Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T02:52:57.129Z Has data issue: false hasContentIssue false
  • English
  • Français

One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights

Published online by Cambridge University Press:  01 July 1999

SVANTE JANSON
SVANTE JANSON
Affiliation:
Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden (e-mail: svante.janson@math.uu.se)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Consider the minimal weights of paths between two points in a complete graph Kn with random weights on the edges, the weights being, for instance, uniformly distributed. It is shown that, asymptotically, this is log n/n for two given points, that the maximum if one point is fixed and the other varies is 2 log n/n, and that the maximum over all pairs of points is 3 log n/n.

Some further related results are given as well, including results on asymptotic distributions and moments, and on the number of edges in the minimal weight paths.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 8 , Issue 4 , July 1999 , pp. 347 - 361
Copyright
1999 Cambridge University Press