Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-24T23:01:26.375Z Has data issue: false hasContentIssue false
  • English
  • Français

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  and
PIET VAN MIEGHEM
GERARD HOOGHIEMSTRA
Affiliation:
Delft University of Technology, Electrical Engineering, Mathematics and Computer Science, PO Box 5031, 2600 GA Delft, The Netherlands (e-mail: [email protected], [email protected])
PIET VAN MIEGHEM
Affiliation:
Delft University of Technology, Electrical Engineering, Mathematics and Computer Science, PO Box 5031, 2600 GA Delft, The Netherlands (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008 , pp. 537 - 548
Copyright
Copyright © Cambridge University Press 2008

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.)

References

[1]Abramowitz, M. and Stegun, I. A. (1968) Handbook of Mathematical Functions, Dover.Google Scholar
[2]Daley, D. J. and Gani, J. (1999) Epidemic Modelling: An Introduction, Studies in Mathematical Biology, Cambridge University Press.Google Scholar
[3]Galambos, J. (1987) The Asymptotic Theory of Extreme Order Statistics, 2nd edn, Krieger.Google Scholar
[4]van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2001) First-passage percolation on the random graph. Probab. Engrg Inform. Sci. (PEIS) 15 225–237.CrossRefGoogle Scholar
[5]van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2002) The flooding time in random graphs. Extremes 5 111–129.CrossRefGoogle Scholar
[6]van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2006) The size and the weight of the shortest path trees with exponential link weights. Combin. Probab. Comput. 16 1–26.Google Scholar
[7]Hooghiemstra, G. and Van Mieghem, P. (2001) Delay distributions on fixed internet paths. Delft University of Technology, report 20011020. www.nas.ewi.tudelft.nl/people/Piet/TUDelftreportsGoogle Scholar
[8]Janson, S. (1999) One, two and three times log n/n for paths in a complete graph with random weights. Combin. Probab. Comput. 8 347–361.CrossRefGoogle Scholar
[9]Van Mieghem, P. (2006) Performance Analysis of Communications Systems and Networks, Cambridge University Press.CrossRefGoogle Scholar
[10]Van Mieghem, P., Hooghiemstra, G. and van der Hofstad, R. (2000) A scaling law for the hopcount. Report, TU-Delft.Google Scholar
[11]Van Mieghem, P. and Tang, S. (2008) Weight of the shortest path to the first encountered peer in a peer group of size m. Probab. Engrg Inform. Sci. (PEIS), 22, 37–52.CrossRefGoogle Scholar