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

DOI10.1214/07-AIHP138zbMath1186.05108arXivmath/0609547MaRDI QIDQ731711

David J. Aldous, Charles Bordenave, Marc Lelarge

Publication date: 8 October 2009

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0609547

zbMATH Keywords

combinatorial optimization; Poisson point process; probabilistic analysis of algorithms; continuum percolation; random geometric graph; local weak convergence; minimal spanning tree; disordered lattice

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C05: Trees

05C80: Random graphs (graph-theoretic aspects)

60K35: Interacting random processes; statistical mechanics type models; percolation theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotics for Euclidean minimal spanning trees on random points
• Probability theory of classical Euclidean optimization problems
• Simultaneous uniqueness of infinite clusters in stationary random labeled graphs
• Weak laws of large numbers in geometric probability
• Percolation and minimal spanning forests in infinite graphs
• The ?(2) limit in the random assignment problem
• Continuum Percolation
• Scaling and universality in continuous length combinatorial optimization