Notice that, Berman et
al [67] gave a 4
3 approximation method to connect a dominating set and Robins
et al [64] gave an 4
3 approximation method to connect an independent set.
Thus, we can easily have an 8
3 approximation algorithm for MCDS. Recently,
Cheng et al. [68] designed a PTAS for MCDS in UDG. However, it is di?±cult
to distributize their method e?±ciently.
Distributed Methods
Many distributed clustering (or dominating set) algorithms have been proposed
in the literature [69??“74]. This subsection is devoted to the distributed
methods that approximate the minimum dominating set and the minimum
connected dominating set for a unit disk graph. In the rest of this subsection,
we will interchange the terms clusterhead and dominator. The node that is
not a clusterhead is also called dominatee.
Clustering without Geometry Property
For general graphs, Jia et al [75] described and analyzed some randomized
distributed algorithms for the minimum dominating set problem that run in
polylogarithmic time, independent of the diameter of the network, and that
return with high probability a dominating set of size that falls within a logarithmic
factor from the optimum. Their best algorithm runs in O(log n log??)
rounds with high probability, and every pair of neighbors exchange a constant
number of messages in each round. The computed dominating set is within
O(log??) in expectation and within O(log n) with high probability.
Pages:
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235