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

Ayalvadi Ganesh, Angus Davidson

Research output: Contribution to journalArticle (Academic Journal)peer-review

1 Citation (Scopus)
191 Downloads (Pure)

Abstract

Consider the complete graph on n 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, whereas the diameter (maximum distance between any two vertices) scales as 3 log n/n. Bollobás, Gamarnik, Riordan and Sudakov showed that, for any fixed k, the weight of the Steiner tree connecting k typical vertices scales as (k − 1)log n/n, which recovers Janson's result for k = 2. We extend this to show that the worst case k-Steiner tree, over all choices of k vertices, has weight scaling as (2k − 1)log n/n and finally, we generalize this result to Steiner trees with a mixture of typical and worst case vertices.
Original languageEnglish
Pages (from-to)826-838
Number of pages13
JournalCombinatorics, Probability and Computing
Volume26
Issue number6
Early online date27 Jul 2017
DOIs
Publication statusPublished - Nov 2017

Fingerprint

Dive into the research topics of 'Maximal Steiner Trees in the Stochastic Mean-Field Model of Distance'. Together they form a unique fingerprint.

Cite this