A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets

Xinyun Wu (), Zhipeng Lü () and Fred Glover ()
Additional contact information
Xinyun Wu: School of Computer Science, Hubei University of Technology, Wuhan 430068, P.R. China
Zhipeng Lü: SMART, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, P.R. China
Fred Glover: Department of Electrical, Computer and Energy Engineering, College of Engineering & Applied Science, University of Colorado Boulder, Boulder, Colorado 80309

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 817-833

Abstract: The minimum connected dominating set (MCDS) problem consists of selecting a minimum set of vertices from an undirected graph, such that each vertex not in this set is adjacent to at least one of the vertices in it, and the subgraph induced by this vertex set is connected. This paper presents a fast vertex weighting (FVW) algorithm for solving the MCDS problem, which integrates several distinguishing features, such as a vertex weighting-based local search with tabu and perturbation strategies to help the search to jump out of the local optima, as well as a search space reduction strategy to improve the search efficiency. Computational experiments on four sets of 112 commonly used public benchmark instances, as well as 15 newly introduced sparse instances, show that FVW is highly competitive compared with the state-of-the-art algorithms in the literature despite its simplicity. FVW improves the previous best-known results for 20 large public benchmark instances while matching the best-known results for all but 2 of the remaining ones. Several ingredients of FVW are investigated to demonstrate the importance of the proposed ideas and techniques. Summary of Contribution: As a challenging classical NP-hard problem, the minimum connected dominating set (MCDS) problem has been studied for decades in the areas of both operations research and computer science, although there does not exist an exact polynomial algorithm for solving it. Thus, the new breakthrough on this classical NP-hard problem in terms of the computational results on classical benchmark instances is significant. This paper presents a new fast vertex weighting local search for solving the MCDS problem. Computational experiments on four sets of 112 commonly used public benchmark instances show that fast vertex weighting (FVW) is able to improve the previous best-known results for 20 large instances while matching the best-known results for all but 2 of the remaining instances. Several ingredients of FVW are also investigated to demonstrate the importance of the proposed ideas and techniques.

Keywords: metaheuristic; minimum dominating set; vertex weighting; local search; search space reduction (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1106 (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:34:y:2022:i:2:p:817-833

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