Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-01-11T23:12:40.575Z Has data issue: false hasContentIssue false
  • English
  • Français

Distribution of Minimal Path Lengths when Edge Lengths are Independent Heterogeneous Exponential Random Variables

Part of: Graph theory Combinatorial probability

Published online by Cambridge University Press:  04 February 2016

Sheldon M. Ross
Sheldon M. Ross*
Affiliation:
University of Southern California
*
∗ Postal address: Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089, USA. Email address: [email protected]
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.

We find the joint distribution of the lengths of the shortest paths from a specified node to all other nodes in a network in which the edge lengths are assumed to be independent heterogeneous exponential random variables. We also give an efficient way to simulate these lengths that requires only one generated exponential per node, as well as efficient procedures to use the simulated data to estimate quantities of the joint distribution.

Keywords

Shortest pathexponential edge lengthjoint distributionsimulation

MSC classification

Primary: 05C80: Random graphs 60C05: Combinatorial probability
Type
Research Article
Information
Journal of Applied Probability , Volume 49 , Issue 3 , September 2012 , pp. 895 - 900
Copyright
© Applied Probability Trust 

Footnotes

This material is based upon work supported by, or in part by, the US Army Research Laboratory and the US Army Research Office under contract\grant number W911NF-11-1-0115.

References

Davis, R. and Prieditis, A. (1993). The expected length of a shortest path. Inform. Process. Lett. 46, 135–141.Google Scholar
Frieze, A. M. and Grimmett, G. R. (1985). The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math. 10, 57–77.Google Scholar
Hassin, R. and Zemel, E. (1985). On shortest paths in graphs with random weights. Math. Operat. Res. 10, 557–564.Google Scholar
Janson, S. (1999). One, two and three times log n/n for paths in a complete graph with random weights. Combinatorics Prob. Comput. 8, 347–361.Google Scholar
Kulkarni, V. G. (1986). Shortest paths in networks with exponentially distributed arc lengths. Networks 16, 255–274.Google Scholar
Ross, S. M. (2010). Introduction to Probability Models, 10th edn. Academic Press, Amsterdam.Google Scholar
Van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2006). Size and weight of shortest path trees with exponential link weights. Combinatorics Prob. Comput. 15, 903–926.Google Scholar