A New Constant Factor Approximation for Computing 3-Connected m-Dominating Sets in Homogeneous Wireless Networks
Authors:
- Donghyun KimDKDonghyun Kim
- Wei WangWWWei Wang
- Xianyue LiXLXianyue Li
- Zhao ZhangZZZhao Zhang
- Weili WuWWWeili Wu
- 1 March 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-9
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.Keywords
This publication has 19 references indexed in Scilit:
- Construction algorithms for k-connected m-dominating sets in wireless sensor networks2008
- Recyclable Connected Dominating Set for Large Scale Dynamic Wireless NetworksLecture Notes in Computer Science, 2008
- Constructing k-Connected m-Dominating Sets in Wireless Sensor Networks2007
- On approximation algorithms of -connected -dominating sets in disk graphsTheoretical Computer Science, 2007
- Minimum connected dominating sets and maximal independent sets in unit disk graphsTheoretical Computer Science, 2006
- A survey on sensor networksIEEE Communications Magazine, 2002
- The broadcast storm problem in a mobile ad hoc network1999
- Approximation Algorithms for Connected Dominating SetsAlgorithmica, 1998
- Unit disk graphsDiscrete Mathematics, 1990
- Approximation algorithms for combinatorial problemsJournal of Computer and System Sciences, 1974