Skip to main content
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

Near-minimal spanning trees: A scaling exponent in probability models


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.
Current View