Localized Spanners for Wireless Networks

Details Localized Spanners for Wireless Networks Localized Spanners for Wireless Networks

2008-06-26

arxiv.org/abs/0806.4221v1

Computer Science

Distributed, Parallel, and Cluster Computing

21 pages

Scientific paper

We present a new efficient localized algorithm to construct, for any given quasi-unit disk graph G=(V,E) and any e > 0, a (1+e)-spanner for G of maximum degree O(1) and total weight O(w(MST)), where w(MST) denotes the weight of a minimum spanning tree for V. We further show that similar localized techniques can be used to construct, for a given unit disk graph G = (V, E), a planar Cdel(1+e)(1+pi/2)-spanner for G of maximum degree O(1) and total weight O(w(MST)). Here Cdel denotes the stretch factor of the unit Delaunay triangulation for V. Both constructions can be completed in O(1) communication rounds, and require each node to know its own coordinates.

Affiliated with

Also associated with

No associations

Rating

Localized Spanners for Wireless Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Localized Spanners for Wireless Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Localized Spanners for Wireless Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-245308