Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models

David Aldous, Charles Bordenave, Marc Lelarge

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 $\delta$ of…