The weight of the shortest path tree

被引：4
作者：
van der Hofstad, Remco
Hooghiemstra, Gerard
Van Mieghem, Piet
机构：
[1] Delft Univ Technol, NL-2600 GA Delft, Netherlands
[2] Eindhoven Univ Technol, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands
来源：
RANDOM STRUCTURES & ALGORITHMS | 2007年 / 30卷 / 03期
关键词：
D O I：
10.1002/rsa.20141
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
The minimal weight of the shortest path tree in a complete graph with independent and exponential (mean 1) random link weights is shown to converge to a Gaussian distribution. We prove a conditional central limit theorem and show that the condition holds with probability converging to 1. (c) 2006 Wiley Periodicals, Inc.
引用
收藏
页码：359 / 379
页数：21
相关论文
共 11 条
[1]   ON AN INTRIGUING INTEGRAL AND SOME SERIES RELATED TO ZETA(4) [J].
BORWEIN, D ;
BORWEIN, JM .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1995, 123 (04) :1191-1198
[2]  
Coppersmith D, 1999, RANDOM STRUCT ALGOR, V15, P113, DOI 10.1002/(SICI)1098-2418(199909)15:2<113::AID-RSA1>3.0.CO
[3]  
2-S
[4]   ON THE VALUE OF A RANDOM MINIMUM SPANNING TREE PROBLEM [J].
FRIEZE, AM .
DISCRETE APPLIED MATHEMATICS, 1985, 10 (01) :47-56
[5]  
GRADSTEYN IS, 1994, TABLES INTEGRALS SER
[6]  
Janson S, 2002, BOLYAI MATH STUD, V10, P289
[7]   THE MINIMAL SPANNING TREE IN A COMPLETE GRAPH AND A FUNCTIONAL LIMIT-THEOREM FOR TREES IN A RANDOM GRAPH [J].
JANSON, S .
RANDOM STRUCTURES & ALGORITHMS, 1995, 7 (04) :337-355
[8]   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
[9]  
VANDERHOFSTAD R, 2006, IN PRESS COMBINATOR
[10]  
VANMIEGHEM P, 2000, 2000125 DELFT U TECH
12