On the connectivity threshold for general uniform metric spaces

DOI10.1016/J.IPL.2010.02.015MaRDI QIDQ656572zbMATH OpenOpenAlexFDO

Authors Gady Kozma, Zvi Lotker, Gideon Stupp

Publication date 18 January 2012

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

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

Mathematics Subject Classification ID

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

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).

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

Cites work

• scientific article; zbMATH DE number 44693 (Why is no real title available?)
• scientific article; zbMATH DE number 1254188 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• scientific article; zbMATH DE number 1369841 (Why is no real title available?)
• A strong law for the longest edge of the minimal spanning tree
• Continuum Percolation
• Hölder regularity and dimension bounds for random curves
• Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
• The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees
• The longest edge of the random minimal spanning tree
• The minimal spanning tree and the upper box dimension
• The scaling limits of near-critical and dynamical percolation

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)