[FoRK] [serval-project-dev] An interesting paper: The Bin-Covering Technique for Thresholding Random Geometric Graph Properties

Eugen Leitl eugen at leitl.org
Mon Oct 24 23:32:44 PDT 2011

----- Forwarded message from jcox <jcox at experiments.com> -----

From: jcox <jcox at experiments.com>
Date: Mon, 24 Oct 2011 15:29:00 -0700 (PDT)
To: serval-project-developers at googlegroups.com
Subject: [serval-project-dev] An interesting paper:  The Bin-Covering
	Technique for Thresholding Random Geometric Graph Properties
Reply-To: serval-project-developers at googlegroups.com

I stumbled across this paper recently & thought it was interesting:


The Bin-Covering Technique for Thresholding Random Geometric Graph 
Properties  (2005)
by S. Muthukrishnan & Gopal Pandurangan


We study the emerging phenomenon of ad hoc, sensor-based communication 
networks. The communication is modeled by the random geometric 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 (asymptotically) tight thresholds for each of these properties. 
Typically, in the past, random geometric 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 random 
geometric graphs motivated by engineering ad hoc networks.

You received this message because you are subscribed to the Google Groups "Serval Project Developers" group.
To view this discussion on the web visit https://groups.google.com/d/msg/serval-project-developers/-/j-RwWuz6Zp8J.
To post to this group, send email to serval-project-developers at googlegroups.com.
To unsubscribe from this group, send email to serval-project-developers+unsubscribe at googlegroups.com.
For more options, visit this group at http://groups.google.com/group/serval-project-developers?hl=en.

----- End forwarded message -----
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE

More information about the FoRK mailing list