An Efficient Local Search Algorithm for the Minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Dominating Set Problem
The minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-dominating set (MKDS) problem, a generalization of the classical minimum dominating set problem, is an important NP-hard combinatorial optimization problem with various applicat...
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
IEEE
2018
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/b53fcef925c64cfcba53693c05b54eb1 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | The minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-dominating set (MKDS) problem, a generalization of the classical minimum dominating set problem, is an important NP-hard combinatorial optimization problem with various applications. First, to alleviate the cycling problem in the local search, a MKDS two-level configuration checking (MKDSCC<sup>2</sup>) strategy is presented. Second, we use the vertex cost scheme to define the scoring mechanism and to improve the solution effectively. Third, by combining MKDSCC<sup>2</sup> strategy and the scoring mechanism, we propose a vertex selection strategy to decide which vertex should be added into or removed from the candidate solution. Based on these strategies, an efficient local search algorithm (VSCC<sup>2</sup>), which incorporates a two-level configuration checking strategy, scoring mechanism, and vertex selection strategy, is proposed. We compare the performance of VSCC<sup>2</sup> with the classic GRASP algorithm and the famous commercial solver CPLEX on the classical instances. The comprehensive results show that the VSCC<sup>2</sup> algorithm is very competitive in terms of solution quality and computing time. |
|---|