A New Approximation Algorithm for Minimum-Weight(1,𝑚)(1,m)–Connected Dominating Set
Jiao Zhou, Yingli Ran, Panos M. Pardalos, Zhao Zhang, Shaojie Tang, Ding-Zhu Du
INFORMS Journal on Computing · 2025 · Volume 37 · Issue 4
Abstract
Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset induces a connected subgraph. Furthermore, if every other node has at least m neighbors in the subset, then the node subset is called a ( 1 , đť‘š ) ( 1 , m ) CDS. The minimum-weight ( 1 , đť‘š ) ( 1 , m ) CDS problem aims at finding a ( 1 , đť‘š ) ( 1 , m ) CDS with minimum total node weight. In this paper, we present a new polynomial-time approximation algorithm for this problem, which improves previous ratio by a factor of 2/3. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant U20A2068] and the National Science Foundation [Grant III-1907472]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0306 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0306 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
Keywords
approximation algorithm, connected dominating set, weight, fault-tolerance
Enable JavaScript for citation tools and additional paper interactions.