Diameter and broadcast time of random geometric graphs in arbitrary dimensions

DOI10.1007/s00453-012-9710-yzbMath1275.05050OpenAlexW2019565283MaRDI QIDQ378238

Tobias Friedrich, Alexandre Stauffer, Thomas Sauerwald

Publication date: 11 November 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://opus.bath.ac.uk/36409/5/Stauffer_Algorithmica.pdf

zbMATH Keywords

diameterrandom geometric graphsgraph distancelargest connected componentrandomized broadcast algorithmrandomized rumor spreading: Euclidean distance

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Communication theory (94A05)

Related Items

On the Diameter of Hyperbolic Random Graphs, On the Diameter of Hyperbolic Random Graphs, On the Push&Pull Protocol for Rumor Spreading, Rumors Spread Slowly in a Small-World Spatial Network, On linear-time data dissemination in dynamic rooted trees, Super-Exponential Extinction Time of the Contact Process on Random Geometric Graphs, Unnamed Item, Topology-hiding computation on all graphs, Space-time percolation and detection by mobile nodes, Robustness of randomized rumour spreading, Detecting a botnet in a network, Topology-Hiding Computation Beyond Logarithmic Diameter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the runtime and robustness of randomized broadcasting
• On mixing and edge expansion properties in randomized broadcasting
• Random geometric graph diameter in the unit ball
• Thresholding random geometric graph properties motivated by ad hoc sensor networks
• The shortest-path problem for graphs with random arc-lengths
• First passage percolation for random colorings of \(\mathbb{Z}^ d\)
• Domination by product measures
• The longest edge of the random minimal spanning tree
• Surface order large deviations for high-density percolation
• On the cover time and mixing time of random geometric graphs
• On the chemical distance for supercritical Bernoulli percolation
• Randomized broadcast in networks
• The cover time of the giant component of a random graph
• Rumor Spreading on Random Regular Graphs and Expanders
• Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs
• On Spreading a Rumor
• Percolation
• Random Geometric Graphs
• Large deviations for discrete and continuous percolation
• Continuum Percolation