Restricted swap-based neighborhood search for the minimum connected dominating set problem

Restricted swap-based neighborhood search for the minimum connected dominating set problem

0.00 Avg rating0 Votes
Article ID: iaor201727
Volume: 69
Issue: 2
Start Page Number: 222
End Page Number: 236
Publication Date: Mar 2017
Journal: Networks
Authors: , ,
Keywords: combinatorial optimization, search, sets, heuristics: local search
Abstract:

The minimum connected dominating set problem (MCDSP) has become increasingly important in recent years due to its applicability to mobile ad hoc networks and sensor grids. This paper presents a restricted swap‐based neighborhood (RSN) tailored for solving MCDSP. This novel neighborhood structure is embedded into tabu Search (TS) and a perturbation mechanism is employed to enhance diversification. The proposed RSN‐TS algorithm is tested on four sets of public benchmark instances widely used in the literature. The results demonstrate the efficacy of the proposed algorithm in terms of both solution quality and computational efficiency. In particular, the RSN‐TS algorithm was able to improve the best known results on 41 out of the 97 problem instances while matching the best known results on all the remaining 56 instances. Furthermore, the article analyzes some key features of the proposed approach in order to identify its critical success factors.

Reviews

Required fields are marked *. Your email address will not be published.