Maximal Steiner Trees in the Stochastic Mean-Field Model of Distance

preprint2015arXivOpen access

Abstract

Consider the complete graph on nn vertices, with edge weights drawn independently from the exponential distribution with unit mean. Janson showed that the typical distance between two vertices scales as log⁡n/n\log{n}/n, whereas the diameter (maximum distance between any two vertices) scales as 3log⁡n/n3\log{n}/n. Bollobás et al. showed that, for any fixed k, the weight of the Steiner tree connecting kk typical vertices scales as (k−1)log⁡n/n(k-1)\log{n}/n, which recovers Janson's result for k=2k=2. We extend this result to show that the worst case kk-Steiner tree, over all choices of kk vertices, has weight scaling as (2k−1)log⁡n/n(2k-1)\log{n}/n and finally, we generalise this result to Steiner trees with a mixture of typical and worst case vertices.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.