A New Approximation Algorithm for Minimum-Weight (1,m)–Connected Dominating Set
INFORMS Journal on Computing · 2025-07 · 37 (4) · 1106-1120
DOI: 10.1287/ijoc.2023.0306 ↗Kurz gefasst
Fachartikel in der Zeitschrift INFORMS Journal on Computing, 2025-07. Verfasst von Jiao Zhou und 5 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 25 Literaturangaben.
Abstract (Originalsprache)
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 [Formula: see text]CDS. The minimum-weight [Formula: see text]CDS problem aims at finding a [Formula: see text]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/ .
Zitieren
APA
Zhou, J., Ran, Y., Pardalos, P. M., Zhang, Z., Tang, S., & Du, D. (2025). A New Approximation Algorithm for Minimum-Weight (1,m)–Connected Dominating Set. INFORMS Journal on Computing, 37(4), 1106-1120. https://doi.org/10.1287/ijoc.2023.0306
Vancouver
Zhou J, Ran Y, Pardalos PM, Zhang Z, Tang S, Du D. A New Approximation Algorithm for Minimum-Weight (1,m)–Connected Dominating Set. INFORMS Journal on Computing. 2025;37(4):1106-1120. doi:10.1287/ijoc.2023.0306
BibTeX
@article{Zhou2025,
author = {Zhou, Jiao and Ran, Yingli and Pardalos, Panos M. and Zhang, Zhao and Tang, Shaojie and Du, Ding-Zhu},
title = {A New Approximation Algorithm for Minimum-Weight (1,m)–Connected Dominating Set},
journal = {INFORMS Journal on Computing},
year = {2025},
volume = {37},
number = {4},
pages = {1106--1120},
doi = {10.1287/ijoc.2023.0306}
}
EUVIMED