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

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

  • Author(s): Aldous, DJ
  • Bordenave, C
  • Lelarge, M
  • et al.

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 Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View