The weight and hopcount of the shortest path in the complete graph with exponential weights

被引：4
作者：
Hooghiemstra, Gerard [1 ]
Van Mieghem, Piet [1 ]
机构：
[1] Delft Univ Technol Elect Engn Math & Comp Sci, NL-2600 GA Delft, Netherlands
来源：
COMBINATORICS PROBABILITY & COMPUTING | 2008年 / 17卷 / 04期
关键词：
Probability;
D O I：
10.1017/S0963548308009176
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Both the hopcount H(N) (the number of links) and the weight W(N) (the sum of the weights on links) of the shortest path between two arbitrary nodes in the complete graph K(N) with i.i.d. exponential link weights is computed. We consider the joint distribution of the pair (H(N), W(N)) and derive, after proper scaling, the joint limiting distribution. One of the results is that H(N) and W(N), properly scaled, are asymptotically independent.
引用
收藏
页码：537 / 548
页数：12
相关论文
共 11 条
[1]  
Abramowitz M, 1968, HDB MATH FUNCTIONS
[2]  
Daley D. J., 1999, STUDIES MATH BIOL
[3]  
Galambos J, 1987, ASYMPTOTIC THEORY EX
[4]  
Hooghiemstra G., 2001, 20011020 DELFT U TEC
[5]   One, two and three times log n/n for paths in a complete graph with random weights [J].
Janson, S .
COMBINATORICS PROBABILITY & COMPUTING, 1999, 8 (04) :347-361
[6]   First-passage percolation on the random graph [J].
van der Hofstad, R ;
Hooghiemstra, G ;
Van Mieghem, P .
PROBABILITY IN THE ENGINEERING AND INFORMATIONAL SCIENCES, 2001, 15 (02) :225-237
[7]  
VAN DER HOFSTAD R., 2002, EXTREMES, V5, P111
[8]   Weight of the shortest path to the first encountered peer in a peer group of size m [J].
Van Mieghem, P. ;
Tang, S. .
PROBABILITY IN THE ENGINEERING AND INFORMATIONAL SCIENCES, 2008, 22 (01) :37-52
[9]  
van Mieghem P., 2000, SCALING LAW HOPCOUNT
[10]  
Van Mieghem P., 2006, Performance analysis of communications networks and systems
12