Finally, they Run a greedy algorithm
in [54] on the planar spanner with bounded degree to bound the total weight
131
Yu Wang
from the weight of MST(V ). They show that the length stretch factor of the
final graph is ((?? + 1)Cdel)2 ?· (1 + ?«), node degree is at most 27 and the total
weight is at most a constant times the weight of MST. The running time of
their algorithm is O(n log n).
Borrowing some ideas from Bose et al ??™s method, in [55], the authors
proposed another simpler centralized method for constructing a low weight
bounded degree planar spanner with better bounds. Their algorithm is similar
to the one in [33]. It first computes the Delaunay triangulation of a set V
of n nodes, Del(V ). Then, it finds an order ?? of V by removing the node with
smallest degree in Del(V ) (tie broken by ID). The first removed node has the
highest order in ??. Repeat this procedure until only the last node is left, and
it has the lowest order in ??. Since the graph is always a planar graph and we
know that the smallest node degree is at most 5. Then, in ordering ??, node u
has at most 5 edges to its predecessors in Del(V ). Let E be the edge set of
Del(V ), and let E??? be the edge set of the desired spanner. Initialize E??? to be
the empty set and all nodes in V are marked as unprocessed. Then, for each
node u in V , following the increasing order of ??, run the third step in Algorithm
1 to add some edges from E to E???.
Pages:
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230