Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T01:58:05.678Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of:Graph theoryOperations research and management scienceCombinatorial probability

Published online by Cambridge University Press:  27 July 2017

A. DAVIDSON and
A. GANESH
A. DAVIDSON
Affiliation:
School of Mathematics, University of Bristol, University Walk, Bristol BS8 1TW, UK (e-mail: angus.davidson@bristol.ac.uk)
A. GANESH
Affiliation:
School of Mathematics, University of Bristol, University Walk, Bristol BS8 1TW, UK (e-mail: a.ganesh@bristol.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

MSC classification

Primary:60C05: Combinatorial probability
Secondary:05C80: Random graphs90B15: Network models, stochastic

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 6 , November 2017, pp. 826 - 838
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Bhamidi, S. and van der Hofstad, R. (2017) Diameter of the stochastic mean-field model of distance. Combin. Probab. Comput. Google Scholar
[2] Bhamidi, S., van der Hofstad, R. and Hooghiemstra, G. (2011) First passage percolation on the Erdős–Rényi random graph. Combin. Probab. Comput. 20 683–707.Google Scholar
[3] Bollobás, B., Gamarnik, D., Riordan, O. and Sudakov, B. (2004) On the value of a random minimum weight Steiner tree. Combinatorica 24 187–207.Google Scholar
[4] Frieze, A. (2004) On random symmetric travelling salesman problems. Math. Oper. Res. 29 878–890.Google Scholar
[5] Frieze, A. M. (1985) On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10 47–56.Google Scholar
[6] van der Hofstad, R., Hooghiemstra, G. and van Mieghem, P. (2006) Size and weight of shortest path trees with exponential link weights. Combin. Probab. Comput. 15 903–926.Google Scholar
[7] Janson, S. (1999) One, two and three times log n/n for paths in a complete graph with random weights. Combin. Probab. Comput. 8 347–361.Google Scholar
[8] Wästlund, J. (2010) The mean field traveling salesman and related problems. Acta Mathematica 204 91–150.Google Scholar