Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-16T15:03:08.795Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)