Variable-depth neighborhood search algorithm for the minimum-connected dominating-set problem
| Autor: | Lingmin Wang, Taoqing Zhou, Xinyun Wu, Zhipeng Lv |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Incremental heuristic search General Computer Science business.industry Best-first search Iterative deepening depth-first search Search algorithm Beam stack search Beam search Guided Local Search Local search (optimization) business Engineering (miscellaneous) Algorithm Mathematics |
| Zdroj: | SCIENTIA SINICA Informationis. 46:445-460 |
| ISSN: | 1674-7267 |
| DOI: | 10.1360/n112015-00128 |
| Popis: | This paper presents a variable-depth neighborhood search (VDNS) algorithm for solving the minimum-connected dominating-set problem. By considering the problem structure of the minimum-connected dominating-set problem, this paper introduces an effective partition-based neighborhood structure, which consists of a series of basic neighborhood moves, restricts the search space to traverse towards more promising search regions, and generates better solutions during the search. This paper also presents two techniques to further improve the search efficiency of the algorithm: pruning the search branch, and the incremental evaluation technique. Applying the proposed VDNS algorithm to solve the 91 public instances used in the literature, VDNS outperforms the reference algorithms in the literature by improving 38 of the best-known results, demonstrating the efficacy of the proposed VDNS algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|