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.
Publié le : 2008-10-15
Classification:
Combinatorial optimization,
Continuum percolation,
Disordered lattice,
Local weak convergence,
Minimal spanning tree,
Poisson point process,
Probabilistic analysis of algorithms,
Random geometric graph,
05C80,
60K35,
68W40
@article{1222261920,
author = {Aldous, David J. and Bordenave, Charles and Lelarge, Marc},
title = {Near-minimal spanning trees: A scaling exponent in probability models},
journal = {Ann. Inst. H. Poincar\'e Probab. Statist.},
volume = {44},
number = {2},
year = {2008},
pages = { 962-976},
language = {en},
url = {http://dml.mathdoc.fr/item/1222261920}
}
Aldous, David J.; Bordenave, Charles; Lelarge, Marc. Near-minimal spanning trees: A scaling exponent in probability models. Ann. Inst. H. Poincaré Probab. Statist., Tome 44 (2008) no. 2, pp. 962-976. http://gdmltest.u-ga.fr/item/1222261920/