%0 Villanova Faculty Authorship
%A Damian, Mirela.
%E Pemmaraju, Sriram V.
%D 2010
%G English
%T Localized Spanners for Wireless Networks.
%U http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175689
%X 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.