Cube Versus Torus Models and the Euclidean Minimum Spanning Tree Constant
Open Access
- 1 May 1993
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 3 (2) , 582-592
- https://doi.org/10.1214/aoap/1177005439
Abstract
We show that the length of the minimum spanning tree through pointsdrawn uniformly from the d-dimensional torus is almost surely asymptoticallyequivalent to the length of the minimum spanning tree through points drawnuniformly from the d-cube. This result implies that the analytical expressionrecently obtained by Avram and Bertsimas for the MST constant in the d-torus model is in fact valid for the traditional d-cube model. We also showthat the number of vertices of degree k for the MST...Keywords
This publication has 0 references indexed in Scilit: