An inequality of Gauss

In this article Gerard Hooghiemstra and Piet van Mieghem explain why the Gauss inequality is overshadowed by the Chebychev inequality. Furthermore, they present a proof of the Gauss inequality in modern notation.

The Weight of the Shortest Path Tree

The minimal weight of the shortest path tree in a complete graph with independent and exponential (mean 1) random link weights, is shown to converge to a Gaussian distribution. We prove a conditional central limit theorem and show that the condition holds with probability converging to 1.

Size and Weight of Shortest Path Trees with Exponential Link Weights

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 (i.e., m = N ? 1) is a uniform recursive...