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.|