Advertisement
Published in:
2007 | OriginalPaper | Chapter
Algorithms for Minimum m-Connected k-Dominating Set Problem
Authors : Weiping Shang, Frances Yao, Pengjun Wan, Xiaodong Hu
Published in: Combinatorial Optimization and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In wireless sensor networks, virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum
m
-connected
k
-dominating set problem, which is a general version of minimum CDS problem with
m
= 1 and
k
= 1. In this paper we will propose some approximation algorithms for this problem that beat the current best performance ratios.