A hybrid repairing method based local search algorithm for solving the minimum weakly connected dominating set problem

Abstract

The minimum weakly connected dominating set (MWCDS) problem is a significant generalization of the minimum dominating set problem. It is a classical combinatorial optimization problem with broad applications. To address this problem, this paper proposes an efficient local search algorithm. Firstly, the algorithm employs novel reduction rules to shrink problem instances. Secondly, it utilizes a dynamic scoring mechanism based on historical information with a “safety” concept for vertex evaluation. Thirdly, it incorporates the two-level configuration checking (CC²) strategy to mitigate cycling issues during the local search process. Furthermore, a hybrid repair method is used to restore weak connectivity of the solution. Moreover, extensive experimental results demonstrate the superior performance of our algorithm and validate the effectiveness of the proposed strategies.

Keywords

Local Search / Minimum Weakly Connected Dominating Set / Reduction Rules / Dynamic Scoring Mechanism

RIGHTS & PERMISSIONS

Higher Education Press 2026

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.