| Title |
An empirical study of the structure of the shortest path tree / |
| Translation of Title |
Svorinio grafo trumpiausiųjų kelių medžio empirinė analizė. |
| Authors |
Bloznelis, Mindaugas ; Radavičius, Irmantas |
| DOI |
10.15388/LMR.2008.18118 |
| Full Text |
|
| Is Part of |
Lietuvos matematikos rinkinys.. Vilnius : Vilniaus universiteto leidykla. 2008, t. 48-49, p. 338-342.. ISSN 0132-2818. eISSN 2335-898X |
| Keywords [eng] |
shortest path tree ; weighted graph ; random weights |
| Abstract [eng] |
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 N3 \geq . . . denote (ordered) sequence of sizes of these trees. We study statistical properties of this sequence for various densities f and large n. |
| Published |
Vilnius : Vilniaus universiteto leidykla |
| Type |
Journal article |
| Language |
English |
| Publication date |
2008 |
| CC license |
|
