This approach has approximation ratio
2(H(??) + 1). The other approach is first approximating the dominating set
133
Yu Wang
and then connecting the dominating set to form a connected dominating set.
They [63] proved that this approach has approximation ratio ln?? + 3.
One can also use the Steiner tree algorithm to connect the dominators.
This straightforward method gives approximation ratio c(H(??)+1), where c
is the approximation ratio for the unweighted Steiner tree problem. Currently,
the best ratio is 1 + ln 3
2 ?‰? 1.55, due to Robins and Zelikovsky [64].
Hunt et al [41] and Marathe et al [62] also studied the approximation of
the maximum independent set and the minimum dominating set for unit disk
graphs. They gave the first PTASs for MDS in UDG. The method is based on
the following observations: a maximal independent set is always a dominating
set; given a square ? with a fixed area, the size of any maximal dominating
set is bounded by a constant C. Assume that there are n nodes in ?. Then,
we can enumerate all sets with size at most C in time ??(nC). Among these
enumerated sets, the smallest dominating set is the minimum dominating set.
Then, using the shifting strategy proposed by Hochbaum [65], they derived a
PTAS for the minimum dominating set problem.
Since we have PTAS for minimum dominating set and the graph V irtG
connecting every pair of dominators within at most 3 hops is connected [66],
we have an approximation algorithm (constructing a minimum spanning tree
V irtG) for MCDS with approximation ratio 3 + ?«.
Pages:
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234