Size and weight of shortest path trees with exponential link weights

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

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)903-926
JournalCombinatorics, Probability and Computing
Volume15
Issue number6
DOIs
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Size and weight of shortest path trees with exponential link weights'. Together they form a unique fingerprint.

  • Cite this