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

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.
24 pages, 3 figures

Keywords

Probability, 05C80; 60K35; 68W40

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/134791

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0609547
 http://arxiv.org/abs/math/0609547

Collections

arXiv