Breaking the O (ln n ) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set

Jiao Zhou (), Zhao Zhang (), Shaojie Tang (), Xiaohui Huang () and Ding-Zhu Du ()
Additional contact information
Jiao Zhou: College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang Province 321004, China
Zhao Zhang: College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang Province 321004, China
Shaojie Tang: Naveen Jindal School of Management, The University of Texas at Dallas, Richardson, Texas 75080
Xiaohui Huang: College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang Province 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, 225-235

Abstract: Finding a connected dominating set (CDS) in a given graph is a fundamental problem and has been studied intensively for a long time because of its application in computer science and operations research, e.g., connected facility location and wireless networks. In some cases, fault-tolerance is desirable. Taking wireless networks as an example, since wireless nodes may fail due to accidental damage or energy depletion, it is desirable that the virtual backbone has some fault-tolerance. Such a problem can be modeled as finding a minimum k -connected m -fold dominating set (( k , m )-CDS) of a graph G = ( V , E ), which is a node set D such that every node outside of D has at least m neighbors in D and the subgraph of G induced by D is k -connected. In this paper, we study the minimum weight (1, m )-CDS problem ((1, m )-MWCDS), and present an ( H ( δ + m ) + 2 H ( δ − 1))-approximation algorithm, where δ is the maximum degree of the graph and H (·) is the Harmonic number. Notice that the state-of-the-art algorithm achieves O (ln( n ))-approximation factor for the (1, 1)-MWCDS problem, where n is the number of nodes. Our work improves this ratio to O (ln δ ) for an even more general problem: (1, m )-MWCDS. Such an improvement also enables us to obtain a (3.67 + α )-approximation for the (1, m )-MWCDS problem on unit disk graph, where α is the performance ratio for the minimum weight m -fold dominating set problem on unit disk graph.

Keywords: connected dominating set; weight; 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 (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0775 (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:225-235

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 ().