A novel local search approach with connected dominating degree-based incremental neighborhood evaluation for the minimum 2-connected dominating set problem

Mao Luo (), Huigang Qin (), Xinyun Wu () and Caiquan Xiong ()
Additional contact information
Mao Luo: Hubei University of Technology
Huigang Qin: Hubei University of Technology
Xinyun Wu: Hubei University of Technology
Caiquan Xiong: Hubei University of Technology

Journal of Combinatorial Optimization, 2024, vol. 47, issue 5, No 2, 26 pages

Abstract: Abstract The minimum connected dominating set problem is widely studied due to its applicability to mobile ad-hoc networks and sensor grids. Its variant the minimum 2-connected dominating set (M-2CDS) problem has become increasingly important because its critical role in designing fault-tolerant network. This paper presents a connected dominating degree-based local search (CDD-LS) tailored for solving the M-2CDS. The proposed algorithm implements an improved swap-based neighborhood structure as well as the corresponding fast neighborhood evaluation method using connected dominating degree data structure. The diversification techniques including tabu strategy and perturbaistion help the search jump out of the local optima improving the efficiency. This study investigates the performance of the CDD-LS algorithm on 38 publicly available benchmark datasets. The results demonstrate that the CDD-LS algorithm significantly improves the best runtime in 19 instances, while providing the equivalent performance in 8 instances. Furthermore, the CDD-LS is tested on 18 newly generated instances to check its capability on large-scale scenarios. To gain a deeper understanding of the algorithm’s effectiveness, an investigation into the key components of the CDD-LS algorithm is conducted.

Keywords: Meta-heuristic; Combinatorial optimization; Minimum 2-connected dominating set; Local search; Incremental neighborhood evaluation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01175-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:47:y:2024:i:5:d:10.1007_s10878-024-01175-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01175-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().