A New Constant Factor Approximation for Computing 3-Connected m-Dominating Sets in Homogeneous Wireless Networks

Authors:
  • DKDonghyun Kim
    Donghyun Kim
  • WWWei Wang
    Wei Wang
  • XLXianyue Li
    Xianyue Li
  • ZZZhao Zhang
    Zhao Zhang
  • WWWeili Wu
    Weili Wu

Abstract
In this paper, we study the problem of constructing quality fault-tolerant Connected Dominating Sets (CDSs)in homogeneous wireless networks, which can be defined as minimum k-Connected m-Dominating Set ((k,m)-CDS) problem in Unit Disk Graphs (UDGs). We found that every existing approximation algorithm for this problem is incomplete for k ¿3 in a sense that it does not generate a feasible solution in some UDGs. Based on these observations, we propose a new polynomial time approximation algorithm for computing (3,m)-CDSs. We also show that our algorithm is correct and its approximation ratio is a constant.

This publication has 19 references indexed in Scilit: