Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T02:57:33.524Z Has data issue: false hasContentIssue false

The Weight and Hopcount of the Shortest Path in the Complete Graph with Exponential Weights

Published online by Cambridge University Press:  01 July 2008

GERARD HOOGHIEMSTRA
Affiliation:
Delft University of Technology, Electrical Engineering, Mathematics and Computer Science, PO Box 5031, 2600 GA Delft, The Netherlands (e-mail: G.Hooghiemstra@ewi.tudelft.nl, P.VanMieghem@ewi.tudelft.nl)
PIET VAN MIEGHEM
Affiliation:
Delft University of Technology, Electrical Engineering, Mathematics and Computer Science, PO Box 5031, 2600 GA Delft, The Netherlands (e-mail: G.Hooghiemstra@ewi.tudelft.nl, P.VanMieghem@ewi.tudelft.nl)
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.

Both the hopcount HN (the number of links) and the weight WN (the sum of the weights on links) of the shortest path between two arbitrary nodes in the complete graph KN with i.i.d. exponential link weights is computed. We consider the joint distribution of the pair (HN, WN) and derive, after proper scaling, the joint limiting distribution. One of the results is that HN and WN, properly scaled, are asymptotically independent.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2008