Computing Minimum k -Connected m -Fold Dominating Set in General Graphs

Zhao Zhang (), Jiao Zhou (), Shaojie Tang (), Xiaohui Huang () and Ding-Zhu Du ()
Additional contact information
Zhao Zhang: College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang, 321004, China
Jiao Zhou: College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang, 321004, China
Shaojie Tang: Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080
Xiaohui Huang: College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang, 321004, China
Ding-Zhu Du: Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75080

INFORMS Journal on Computing, 2018, vol. 30, issue 2, 217-224

Abstract: Connected dominating set (CDS) problem has been extensively studied in the literature due to its applications in many domains, including computer science and operations research. For example, CDS has been recommended to serve as a virtual backbone in wireless sensor networks (WSNs). Since sensor nodes in WSNs are prone to failures, it is important to build a fault-tolerant virtual backbone that maintains a certain degree of redundancy. A fault-tolerant virtual backbone can be modeled as a k -connected m -fold dominating set ( k , m )-CDS. For a connected graph G = ( V , E ) and two fixed integers k and m , a node set C ⊆ V is a ( k , m )-CDS of G if every node in V \ C has at least m neighbors in C , and the subgraph of G induced by C is k -connected. Previous to this work, approximation algorithms with guaranteed performance ratio in a general graph were known only for k ≤ 3. This paper makes significant progress by presenting a (2 k − 1) α 0 approximation algorithm for general k and m with m ≥ k , where α 0 is the performance ratio for the minimum (1, m )-CDS problem. Using a currently best-known ratio for α 0 , our algorithm has performance ratio O (lnΔ), where Δ is the maximum degree of the graph. Simulation results validate the effectiveness of our algorithm.

Keywords: wireless sensor network; connected dominating set; fault tolerance; approximation algorithm (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0776 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:2:p:217-224

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().