The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “The lower tail of the random minimum spanning tree.”

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

David J. Aldous, Charles Bordenave, Marc Lelarge (2008)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

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+( ). We prove this in the model of the lattice with random edge-lengths and in the euclidean model.