Skip to main content
Open Access Publications from the University of California
Notice: eScholarship will undergo scheduled maintenance from Tuesday, January 21 to Wednesday, January 22. Some functionality may not be available during this time. Learn more at eScholarship Support.
Download PDF
- Main
Near-minimal spanning trees: A scaling exponent in probability models
Published Web Location
https://doi.org/10.1214/07-aihp138Abstract
We study the relation between the minimal spanning tree (MST) on many random points and the "near-minimal" tree which is optimal subject to the constraint that a proportion 8 of its edges must be different from those of the MST. Heuristics suggest that, regardless of details of the probability model, the ratio of lengths should scale as 1 + 0 (δ2). We prove this scaling result in the model of the lattice with random edge-lengths and in the Euclidean model. © Association des Publications de l'Institut Henri Poincaré, 2008.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.
Main Content
For improved accessibility of PDF content, download the file to your device.
Enter the password to open this PDF file:
File name:
-
File size:
-
Title:
-
Author:
-
Subject:
-
Keywords:
-
Creation Date:
-
Modification Date:
-
Creator:
-
PDF Producer:
-
PDF Version:
-
Page Count:
-
Page Size:
-
Fast Web View:
-
Preparing document for printing…
0%