On the value of a random minimum spanning tree problem
type: Item
instance of: scholarly article
title: On the value of a random minimum spanning tree problem
zbMATH Open document ID: 0578.05015
DOI: 10.1016/0166-218X(85)90058-7
published in: Discrete Applied Mathematics
publication date: 1985-01-01T00:00:00Z
review text: The lengths of the edges in a complete graph of order n are independent identically distributed random variables. Under mild conditions the length of the minimum spanning tree is shown to converge in probability as \(n\to \infty\), and the limiting value of the expected length is determined.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 3924796
zbMATH Keywords: edge length
zbMATH Keywords: complete graph
zbMATH Keywords: minimum spanning tree
author: Alan Frieze
MaRDI profile type: Publication
Wikidata QID: Q56484417
cites work: Q3286850
cites work: On the connectivity of random m-orientable graphs and digraphs
cites work: On the shortest spanning subtree of a graph and the traveling salesman problem
cites work: Optimization Problems on Graphs with Independent Random Edge Weights
cites work: On the Expected Value of a Random Assignment Problem
DBLP publication ID: journals/dam/Frieze85
description: scientific article; zbMATH DE number 3924796