On the value of a random minimum weight Steiner tree
type: Item
instance of: scholarly article
title: On the value of a random minimum weight Steiner tree
zbMATH Open document ID: 1056.05125
author: Béla Bollobás
author: David Gamarnik
author: Oliver Riordan
author: Benny Sudakov
published in: Combinatorica
publication date: 2005-02-14T00:00:00Z
review text: Let the edge weights of the complete graph on \(n\) vertices be chosen randomly and independently from an exponential distribution with parameter 1. Fix \(k=o(n)\) vertices. The weight of the minimum weight Steiner tree containing these vertices is approaching \((k-1)(\log n-\log k)/n\) with probability converging to 1.
reviewed by: Péter Komjáth
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 2133932
zbMATH Keywords: random graphs
MaRDI profile type: Publication
full work available at URL: s00493-004-0013-z
OpenAlex ID: W1996753220
DOI: 10.1007/S00493-004-0013-Z
description: scientific article; zbMATH DE number 2133932