Premium
The weight of the shortest path tree
Author(s) -
van der Hofstad Remco,
Hooghiemstra Gerard,
Van Mieghem Piet
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20141
Subject(s) - mathematics , shortest path problem , combinatorics , limit (mathematics) , random graph , tree (set theory) , discrete mathematics , central limit theorem , path (computing) , gaussian , struct , exponential function , graph , statistics , computer science , mathematical analysis , physics , quantum mechanics , programming language
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. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007