Open AccessAn empirical study of the structure of the shortest path tree
Author(s) -
Mindaugas Bloznelis,
Irmantas Radavičius
Publication year - 2008
Publication title -
lietuvos matematikos rinkinys
Language(s) - English
Resource type - Journals
eISSN - 2335-898X
pISSN - 0132-2818
DOI - 10.15388/lmr.2008.18118
Subject(s) - combinatorics , mathematics , vertex (graph theory) , path (computing) , tree (set theory) , sequence (biology) , random tree , graph , shortest path problem , shortest path tree , random variable , random graph , discrete mathematics , statistics , computer science , motion planning , artificial intelligence , biology , robot , genetics , programming language
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.