Size and weight of shortest path trees with exponential link weights

R.W. Hofstad, van der, G. Hooghiemstra, P. Van Mieghem

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

17 Citaten (Scopus)

Samenvatting

We derive the distribution of the number of links and the average weight for the shortest path tree (SPT) rooted at an arbitrary node to $m$ uniformly chosen nodes in the complete graph of size $N$ with i.i.d. exponential link weights. We rely on the fact that the full shortest path tree to all destinations (ie, $m=N-1$) is a uniform recursive tree to derive a recursion for the generating function of the number of links of the SPT, and solve this recursion exactly. The explicit form of the generating function allows us to compute the expectation and variance of the size of the subtree for all $m$. We also obtain exact expressions for the average weight of the subtree.
Originele taal-2Engels
Pagina's (van-tot)903-926
TijdschriftCombinatorics, Probability and Computing
Volume15
Nummer van het tijdschrift6
DOI's
StatusGepubliceerd - 2006

Vingerafdruk Duik in de onderzoeksthema's van 'Size and weight of shortest path trees with exponential link weights'. Samen vormen ze een unieke vingerafdruk.

Citeer dit