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's open access policies. Let us know how this access is important for you.

Main Content
Current View