Localized Spanners for Wireless Networks.

We present a new efficient localized algorithm to construct, for any given quasi-unit disk graph G = (V,E) and any " > 0, a (1+ ")- spanner for G of maximum degree O(1) and total weight O(!(MST)), where !(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+")(1+π 2 )-spanner for G of maximum degree O(1) and total weight O(!(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.

Main Author: Damian, Mirela.
Other Authors: Pemmaraju, Sriram V.
Format: Villanova Faculty Authorship
Language: English
Published: 2010
Online Access: http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175689