A New Approximation Algorithm for Minimum-Weight ( 1, m ) –Connected Dominating Set

Jiao Zhou (), Yingli Ran (), Panos M. Pardalos (), Zhao Zhang (), Shaojie Tang () and Ding-Zhu Du ()
Additional contact information
Jiao Zhou: School of Mathematical Sciences, Zhejiang Normal University, Jinhua, Zhejiang 321004, China
Yingli Ran: School of Mathematical Sciences, Zhejiang Normal University, Jinhua, Zhejiang 321004, China
Panos M. Pardalos: Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Zhao Zhang: School of Mathematical Sciences, Zhejiang Normal University, Jinhua, Zhejiang 321004, China
Shaojie Tang: Department of Management Science and Systems, University at Buffalo, Buffalo, New York 14260
Ding-Zhu Du: Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75080

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 1106-1120

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 , m ) CDS. The minimum-weight ( 1 , m ) CDS problem aims at finding a ( 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.

Keywords: approximation algorithm; connected dominating set; weight; fault-tolerance (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0306 (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:37:y:2025:i:4:p:1106-1120

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