Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models
| dc.creator | Aldous, David | |
| dc.creator | Bordenave, Charles | |
| dc.creator | Lelarge, Marc | |
| dc.date | 2006-09-20 | |
| dc.date | 2007-07-23 | |
| dc.date.accessioned | 2026-07-07T08:19:32Z | |
| dc.date.available | 2026-07-07T08:19:32Z | |
| dc.description | 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 $δ$ 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 + Θ(δ^2)$. We prove this scaling result in the model of the lattice with random edge-lengths and in the Euclidean model. | |
| dc.description | 24 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/math/0609547 | |
| dc.identifier | http://arxiv.org/abs/math/0609547 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134791 | |
| dc.subject | Probability | |
| dc.subject | 05C80; 60K35; 68W40 | |
| dc.title | Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models | |
| dc.type | text |