An empirical study of the structure of the shortest path tree
Articles
Mindaugas Bloznelis
Vilnius University
Irmantas Radavičius
Vilnius University
Published 2008-12-21
https://doi.org/10.15388/LMR.2008.18118
PDF

Keywords

shortest path tree
weighted graph
random weights

How to Cite

Bloznelis M. and Radavičius I. (2008) “An empirical study of the structure of the shortest path tree”, Lietuvos matematikos rinkinys, 48(proc. LMS), pp. 338–342. doi: 10.15388/LMR.2008.18118.

Abstract

We consider a complete graph on n vertices. Edges of the graph are prescribed random positive weights X1, X2, . . ., Xm. Here m = (n/2). We assume that these random variables are independent and have the common probability distribution with density function f (x), x \geq 0. Given a vertex v let T denote the shortest path tree with root v. Let T1, T2, . . . ⊂ T denote the trees that are obtained from T after removal of  the root v. Let N1 \geq N2 \geq  N\geq . . . denote (ordered) sequence of sizes of these trees. We study statistical properties of this sequence for various densities f and large n.

PDF
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Please read the Copyright Notice in Journal Policy