Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T17:25:19.112Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Operations research and management science Graph theory Combinatorial 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: [email protected])
A. GANESH
Affiliation:
School of Mathematics, University of Bristol, University Walk, Bristol BS8 1TW, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05C80: Random graphs 90B15: Network models, stochastic
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 6 , November 2017 , pp. 826 - 838
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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