[FoRK] [serval-project-dev] An interesting paper: The Bin-Covering Technique for Thresholding Random Geometric Graph Properties
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
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