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

被引：11

作者：

Wu, Xinyun ^{[1
]}

Lue, Zhipeng ^{[1
]}

Galinier, Philippe ^{[2
]}

机构：

[1] Huazhong Univ Sci & Technol, Sch Comp Sci & Technol, Lab Smart Comp & Optimizat, Wuhan 430074, Peoples R China

[2] Ecole Polytech Montreal, Dept Genie Informat & Genie Iogiciel, Montreal, PQ, Canada

来源：

NETWORKS | 2017年 / 69卷 / 02期

基金：

中国国家自然科学基金;

关键词：

meta-heuristic; optimization; connected dominating set; swap-based neighborhood structure; tabu search; perturbation operator; BREAKOUT LOCAL SEARCH; WIRELESS AD HOC; VIRTUAL BACKBONE; ALGORITHM; CONSTRUCTION; CUT;

D O I：

10.1002/net.21728

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2016 Wiley Periodicals, Inc.

引用

页码：222 / 236

页数：15

共 33 条

[1]

Balasundaram Balabhaskar, 2006, Handb. Optim. Telecommun., P865, DOI [10.1007/978-0-387-30165-5_30, DOI 10.1007/978-0-387-30165-5_30, 10.1007/978-0-387-30165-530, DOI 10.1007/978-0-387-30165-530]

[2] Breakout Local Search for the Max-Cut problem [J].