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 optimizationPoisson point processprobabilistic analysis of algorithmscontinuum percolationrandom geometric graphlocal weak convergenceminimal spanning treedisordered lattice

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Related Items (1)

The planted matching problem: phase transitions and exact results

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

This page was built for publication: Near-minimal spanning trees: A scaling exponent in probability models