For each edge uv ??? MST(NRNG???
2 (u)), node u tells node v about
this directed edge. Node u keeps an edge uv if uv ??? MST(NRNG???
2 (u)) or
vu ??? MST(NRNG???
2 (v)). Let IMRG+ be the final structure formed by all edges
kept. Similarly, the final structure is called IMRG??’ when edge uv ??? RNG???
is kept i?® uv ??? MST(NRNG???
2 (u)) and uv ??? MST(NRNG???
2 (v)). Here IMRG is
the abbreviation of Incident MST and RNG Graph.
In the algorithm, node u constructs the local minimum spanning tree
MST(NRNG???
2 (u)) based on the induced UDG of the point sets NRNG???
2 (u). It is
obvious that its communication cost is at most 7n. In [48,50], Li et al showed
that structures IMRG+ and IMRG??’ are still connected, planar, of bounded
degree, and low-weight. Clearly, the constructed structures are a supergraph
of the previous structures, i.e., LSMT+
2 ??† IMRG+ and LSMT??’2 ??† IMRG??’,
since this algorithm uses less information than the algorithm of LMST2 in
constructing the local minimum spanning tree.
3.2 Low-Weight Spanners
Notice that all above localized low-weight structures are not spanners. The
spanner property and low-weight property are not easy to be achieved at
the same time. Intuitively, the spanner property requires one to keep more
links, while the low-weight property requires one to keep fewer links from the
original graph. As of now there is no e?±cient distributed algorithm that can
achieve all following desirable features: bounded degree, planar, low weight
and spanner.
Pages:
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228