Until all nodes are processed, the
final graph is formed by edges E???. Finally, run the greedy spanner algorithm
by Gudmundsson et al [54] to bound the weight of the graph. Li et al [55]
proved that given a set V of n points in a two-dimensional plane, the above
O(n log n)-time algorithm constructs a graph (1) that is planar; (2) that is
a t-spanner, for t = (max{??
2 , ?? sin ?®
2 + 1} ?· Cdel)2(1 + ?«); (3) in which each
point of V has degree at most 19 + ???2??
?® ??‰; (4) and whose total edge weight
is bounded from above by a constant factor1 of the weight of the Euclidean
minimum spanning tree of V . Here 0 < ?± < ??/2 is an adjustable parameter.
The time complexity of the algorithm is O(n log n), the same as the method
by Bose et al [53]. However, it has smaller bounded node degree, and it has
potential to become a localized version for wireless sensor networks applicaperformed
in a local way.
Most recently, Li et al [56] proposed the first distributed method to construct
a new bounded degree planar spanner which is also low-weighted.
They first proposed a new bounded degree planar power-spanner called
S??GG, which is similar with SY aoGG [46] except using a new concept of
??-dominating region instead of the fixed cones. Then, they described a novel
distributed algorithm to build a low-weight structure from S??GG by removing
some of its edges. The removing process is carefully designed so that it
does not destroy the spanner property and other nice properties.
Pages:
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231