It was proved in [49] that RNG??? has a maximum
node degree 6 and still contains a MST as a subgraph. However, RNG??? is still
not a low-weight structure.
The localized algorithm given in [49] that constructs a low-weight structure
using only two-hops information is as follows. First, all nodes together
construct the graph of RNG??? in a localized manner. Each node u locally broadcasts
its incident edges in RNG??? to its one-hop neighbors. Assume node u received
a message informing existence of edge xy ??? RNG??? from its neighbor x.
For each edge uv ??? RNG???, if uv is the longest among uv, xy, ux, and vy, node
u removes edge uv. Ties are broken by the label of the edges. Here assume
that uvyx is the convex hull of u, v, x, and y. Let H be the final structure
formed by all remaining edges in RNG???.
Obviously, if an edge uv is kept by node u, then it is also kept by node v.
Li [49] proved that the total edge weight of H is within a constant factor of that
of the minimum spanning tree. This was proved by showing that the edges in
H satisfy the isolation property (defined in [51]). He also showed that the final
structure contains MST of UDG as a subgraph and the communication cost
129
Yu Wang
of the algorithm is at most 7n. The computational cost could be high since
for each link uv ??? RNG???, node u has to test whether there is an edge xy ??? RNG??? and x ??? N1(u) such that uv is the longest among uv, xy, ux, and vy.
Pages:
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225