Recently, Li
et al [48??“50] proposed three localized structures which are low weight, planar
and have bounded node degree. Building these low weight structures uses
partial 2-hop information for each node.
Low-Weight Structure Based on RNG???
In [49], Li proposed the first localized method to construct a structure
H with weight O(?‰(MST)) using total O(n) local-broadcast messages. The
method is based on a modified relative neighborhood graph. Traditionally,
the relative neighborhood graph will always select an edge uv even if there is
some node on the boundary of lune(u, v). Thus, RNG may have unbounded
node degree, e.g., the example in Figure 3(a). Notice that for the sake of
lowering the weight of a structure, the structure should contain as few edges as
possible without breaking the connectivity. Li [49] then naturally extended the
traditional definition of RNG as follows. The modified relative neighborhood
graph consists of all edges uv such that (1) the interior of lune(u, v) contains
no point w ??? V and, (2) there is no point w ??? V with ID(w) < ID(v)
on the boundary of lune(u, v) and kwvk < kuvk, and (3) there is no point
w ??? V with ID(w) < ID(u) on the boundary of lune(u, v) and kwuk <
kuvk, and (4) there is no point w ??? V on the boundary of lune(u, v) with
ID(w) < ID(u), ID(w) < ID(v), and kwuk = kuvk. Li called such a structure
RNG???. Obviously, RNG??? is a subgraph of a traditional RNG and it still can be
constructed using n messages.
Pages:
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224