The weight of the shortest path tree

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 02 Oct 2006 Netherlands English Publisher:WileyJournal:Random Structures & Algorithms, volume 30, pages 359-379 (issn: 1042-9832, eissn: 1098-2418,

Copyright policy )

Authors: Remco van der Hofstad; Gerard Hooghiemstra; Piet Van Mieghem;

doi: 10.1002/rsa.20141

The weight of the shortest path tree

- Summary
- Subjects
- Metrics

Abstract

AbstractThe 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

Country

Netherlands

Related Organizations

Eindhoven University of Technology
Netherlands
Delft University of Technology
Netherlands
Technical University Eindhoven
Netherlands

Keywords

Graph algorithms (graph-theoretic aspects), probability, Gaussian distribution, central limit theorem, Central limit and other weak theorems, random link weights, Trees

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average