### 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 language | English |
---|---|

Pages (from-to) | 903-926 |

Journal | Combinatorics, Probability and Computing |

Volume | 15 |

Issue number | 6 |

DOIs | |

Publication status | Published - 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

Hofstad, van der, R. W., Hooghiemstra, G., & Van Mieghem, P. (2006). Size and weight of shortest path trees with exponential link weights.

*Combinatorics, Probability and Computing*,*15*(6), 903-926. https://doi.org/10.1017/S0963548306007802