Premium
Restricted swap‐based neighborhood search for the minimum connected dominating set problem
Author(s) -
Wu Xinyun,
Lü Zhipeng,
Galinier Philippe
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21728
Subject(s) - computer science , swap (finance) , tabu search , mathematical optimization , benchmark (surveying) , algorithm , mathematics , geodesy , finance , economics , geography
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. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(2), 222–236 2017