[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:

   http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.134.8298

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

Abstract:

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