Thresholding random geometric graph properties motivated by ad hoc sensor networks

DOI10.1016/j.jcss.2010.01.002zbMath1210.05159OpenAlexW1975478958MaRDI QIDQ988583

J. Martínez

Publication date: 18 August 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.01.002

zbMATH Keywords

thresholdsconnectivitycoveragerandom geometric graphsstretchlocal algorithmsensor network models

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Concentration for Poisson functionals: component counts in random geometric graphs ⋮ Concentration for Poisson \(U\)-statistics: subgraph counts in random geometric graphs ⋮ Diameter and broadcast time of random geometric graphs in arbitrary dimensions

Cites Work

• A log log law for maximal uniform spacings
• Probability approximations via the Poisson clumping heuristic
• Randomization and approximation techniques in computer science. 2nd international workshop, RANDOM '98. Barcelona, Spain, October 8--10, 1998. Proceedings
• The longest edge of the random minimal spanning tree
• The connectivity of a graph on uniform points on [0,\,1\(^{d}\).]
• On properties of geometric random problems in the plane
• The small-world phenomenon
• Critical Density Thresholds in Distributed Wireless Networks
• Sharp thresholds For monotone properties in random geometric graphs
• Percolation
• The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1^d]
• The Minimum Vertex Degree of a Graph on Uniform Points in [0, 1^d]
• Random Geometric Graphs
• The capacity of wireless networks
• Approximating the Stretch Factor of Euclidean Graphs
• Paths in graphs
• Efficient communication in an ad-hoc network
• Continuum Percolation
• Graph Drawing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item