The bin-covering technique for thresholding random geometric graph properties

S. Muthukrishnan, Gopal Pandurangan

Research output: Contribution to conferencePaperpeer-review

52 Scopus citations

Abstract

We study the emerging phenomenon of ad hoc, sensor-based communication networks. The communication is modeled by the geometric random graph model G(n, r,ℓ) where n points randomly placed within [0, ℓ]d form the nodes, and any two nodes that correspond to points at most distance r away from each other are connected. We study fundamental properties of G(n, r, ℓ) of interest: connectivity, coverage, and routing-stretch. Our main contribution is a simple analysis technique we call bin-covering that we apply uniformly to get first known, (asymptotically) tight thresholds for each of these properties. Typically, in the past, geometric random graph analyses involved sophisticated methods from continuum percolation theory; on contrast, our bin-covering approach is discrete and very simple, yet it gives us tight threshold bounds. The technique also yields algorithmic benefits as illustrated by a simple local routing algorithm for finding paths with low stretch. Our specific results should also prove interesting to the networking community that has seen a recent increase in the study of geometric random graphs motivated by engineering ad hoc networks.

Original languageEnglish (US)
Pages989-998
Number of pages10
StatePublished - Jul 1 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period1/23/051/25/05

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The bin-covering technique for thresholding random geometric graph properties'. Together they form a unique fingerprint.

Cite this