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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom