On the connectivity threshold for general uniform metric spaces

DOI10.1016/J.IPL.2010.02.015zbMATH Open1229.68078arXivmath/0604261OpenAlexW2066458074MaRDI QIDQ656572FDOQ656572

Gady Kozma, Zvi Lotker, Gideon Stupp

Publication date: 18 January 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: For a measure mu supported on a compact connected subset of a Euclidean space which satisfies a uniform d-dimensional decay of the volume of balls we show that the maximal edge in the minimum spanning tree of n indepndent samples from mu is, with high probability (log n/n)^(1/d).

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

Recommendations

• A strong law for the longest edge of the minimal spanning tree
• Publication:4887376
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• The minimal spanning tree and the upper box dimension
• The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach

Mathematics Subject Classification ID

Trees (05C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Connectivity (05C40)

Cites Work

• Hölder regularity and dimension bounds for random curves
• Title not available (Why is that?)
• A strong law for the longest edge of the minimal spanning tree
• Title not available (Why is that?)
• Title not available (Why is that?)
• Continuum Percolation
• The longest edge of the random minimal spanning tree
• The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees
• The scaling limits of near-critical and dynamical percolation
• The minimal spanning tree and the upper box dimension
• Title not available (Why is that?)
• Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space

Cited In (4)

• An average case analysis of the minimum spanning tree heuristic for the power assignment problem
• Probabilistic connectivity threshold for directional antenna widths
• Fractal dimension and the persistent homology of random geometric complexes
• Probabilistic Connectivity Threshold for Directional Antenna Widths

This page was built for publication: On the connectivity threshold for general uniform metric spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q656572)