The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach
type: Item
instance of: scholarly article
title: The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach
zbMATH Open document ID: 0755.60011
author: F. Avram
author: Dimitris Bertsimas
published in: The Annals of Applied Probability
publication date: 1992-06-28T00:00:00Z
review text: Given \(n\) uniformly and independently distributed points in the \(d\)- dimensional cube of unit volume, it is well established that the length of the minimum spanning tree (MST) on these \(n\) points is asymptotic to \(\beta_{\text{MST}}(d)\cdot n^{(d-1)/d}\), where the constant \(\beta_{\text{MST}}(d)\) depends only on the dimension \(d\). One of the important open problems in this area is the exact determination of \(\beta_{\text{MST}}\). The paper is structured as follows. In Section 2 the authors introduce conditions under which the MST constant is characterized as a series expansion. In Section 3 the authors obtain an exact expression for \(\beta_{\text{MST}}(d)\) on a torus. In Sections 4, 5 an expansion for \(\beta_{\text{MST}}(d)\) in the independent model and better bounds for the MST in the plane are found. The last section includes some concluding remarks.
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 36421
zbMATH Keywords: maximum spanning tree torus
zbMATH Keywords: independent model
reviewed by: Viktor Ohanyan
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1177005773
OpenAlex ID: W1996075091
DOI: 10.1214/AOAP/1177005773
description: scientific article; zbMATH DE number 36421