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 kSteiner 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 language  English 

Pages (fromto)  826838 
Number of pages  13 
Journal  Combinatorics, Probability and Computing 
Volume  26 
Issue number  6 
Early online date  27 Jul 2017 
DOIs  
Publication status  Published  Nov 2017 
Fingerprint
Dive into the research topics of 'Maximal Steiner Trees in the Stochastic MeanField Model of Distance'. Together they form a unique fingerprint.Profiles

Dr A J Ganesh
 School of Mathematics  Associate Professor
 Statistical Science
 Probability, Analysis and Dynamics
 Cabot Institute for the Environment
 Probability
Person: Academic , Academic , Member