Diameter and broadcast time of random geometric graphs in arbitrary dimensions

Tobias Friedrich, Thomas Sauerwald, A Stauffer

Research output: Contribution to journalArticle

15 Citations (Scopus)
68 Downloads (Pure)

Abstract

A random geometric graph (RGG) is defined by placing n points uniformly at random in [0,n 1/d ]d, and joining two points by an edge whenever their Euclidean distance is at most some fixed r. We assume that r is larger than the critical value for the emergence of a connected component with Ω(n) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of ω (logn/r1/d), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is Θ(n1/d/r) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within Θ(n 1/d /r+logn) rounds.
Original languageEnglish
Pages (from-to)65-88
Number of pages24
JournalAlgorithmica
Volume67
Issue number1
DOIs
Publication statusPublished - 1 Sep 2013

Fingerprint

Random Geometric Graph
Broadcast
Euclidean Distance
Connected Components
Arbitrary
Vertex of a graph
Joining
Graph Distance
Critical value
Choose
Imply

Cite this

Diameter and broadcast time of random geometric graphs in arbitrary dimensions. / Friedrich, Tobias; Sauerwald, Thomas; Stauffer, A.

In: Algorithmica, Vol. 67, No. 1, 01.09.2013, p. 65-88.

Research output: Contribution to journalArticle

Friedrich, Tobias ; Sauerwald, Thomas ; Stauffer, A. / Diameter and broadcast time of random geometric graphs in arbitrary dimensions. In: Algorithmica. 2013 ; Vol. 67, No. 1. pp. 65-88.
@article{8f9722580a0a42149a3b209bf01c5598,
title = "Diameter and broadcast time of random geometric graphs in arbitrary dimensions",
abstract = "A random geometric graph (RGG) is defined by placing n points uniformly at random in [0,n 1/d ]d, and joining two points by an edge whenever their Euclidean distance is at most some fixed r. We assume that r is larger than the critical value for the emergence of a connected component with Ω(n) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of ω (logn/r1/d), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is Θ(n1/d/r) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within Θ(n 1/d /r+logn) rounds.",
author = "Tobias Friedrich and Thomas Sauerwald and A Stauffer",
year = "2013",
month = "9",
day = "1",
doi = "10.1007/s00453-012-9710-y",
language = "English",
volume = "67",
pages = "65--88",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "1",

}

TY - JOUR

T1 - Diameter and broadcast time of random geometric graphs in arbitrary dimensions

AU - Friedrich, Tobias

AU - Sauerwald, Thomas

AU - Stauffer, A

PY - 2013/9/1

Y1 - 2013/9/1

N2 - A random geometric graph (RGG) is defined by placing n points uniformly at random in [0,n 1/d ]d, and joining two points by an edge whenever their Euclidean distance is at most some fixed r. We assume that r is larger than the critical value for the emergence of a connected component with Ω(n) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of ω (logn/r1/d), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is Θ(n1/d/r) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within Θ(n 1/d /r+logn) rounds.

AB - A random geometric graph (RGG) is defined by placing n points uniformly at random in [0,n 1/d ]d, and joining two points by an edge whenever their Euclidean distance is at most some fixed r. We assume that r is larger than the critical value for the emergence of a connected component with Ω(n) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of ω (logn/r1/d), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is Θ(n1/d/r) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within Θ(n 1/d /r+logn) rounds.

UR - http://www.scopus.com/inward/record.url?scp=84880227234&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1007/s00453-012-9710-y

U2 - 10.1007/s00453-012-9710-y

DO - 10.1007/s00453-012-9710-y

M3 - Article

VL - 67

SP - 65

EP - 88

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 1

ER -