An Efficient Local Search Algorithm for the Minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Dominating Set Problem

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Ruizhi Li, Huan Liu, Xiaoli Wu, Jun Wu, Minghao Yin
Formato: article
Lenguaje:EN
Publicado: IEEE 2018
Materias:
Heuristic
local search
minimum <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k</italic>-dominating set problem
Electrical engineering. Electronics. Nuclear engineering
TK1-9971
Acceso en línea:https://doaj.org/article/b53fcef925c64cfcba53693c05b54eb1
Etiquetas: Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
id oai:doaj.org-article:b53fcef925c64cfcba53693c05b54eb1
record_format dspace
spelling oai:doaj.org-article:b53fcef925c64cfcba53693c05b54eb12021-11-19T00:02:10ZAn Efficient Local Search Algorithm for the Minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Dominating Set Problem2169-353610.1109/ACCESS.2018.2875499https://doaj.org/article/b53fcef925c64cfcba53693c05b54eb12018-01-01T00:00:00Zhttps://ieeexplore.ieee.org/document/8492522/https://doaj.org/toc/2169-3536The 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.Ruizhi LiHuan LiuXiaoli WuJun WuMinghao YinIEEEarticleHeuristiclocal searchminimum <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k</italic>-dominating set problemElectrical engineering. Electronics. Nuclear engineeringTK1-9971ENIEEE Access, Vol 6, Pp 62062-62075 (2018)
institution DOAJ
collection DOAJ
language EN
topic Heuristic
local search
minimum <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k</italic>-dominating set problem
Electrical engineering. Electronics. Nuclear engineering
TK1-9971
spellingShingle Heuristic
local search
minimum <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k</italic>-dominating set problem
Electrical engineering. Electronics. Nuclear engineering
TK1-9971
Ruizhi Li
Huan Liu
Xiaoli Wu
Jun Wu
Minghao Yin
An Efficient Local Search Algorithm for the Minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Dominating Set Problem
description 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.
format article
author Ruizhi Li
Huan Liu
Xiaoli Wu
Jun Wu
Minghao Yin
author_facet Ruizhi Li
Huan Liu
Xiaoli Wu
Jun Wu
Minghao Yin
author_sort Ruizhi Li
title An Efficient Local Search Algorithm for the Minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Dominating Set Problem
title_short An Efficient Local Search Algorithm for the Minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Dominating Set Problem
title_full An Efficient Local Search Algorithm for the Minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Dominating Set Problem
title_fullStr An Efficient Local Search Algorithm for the Minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Dominating Set Problem
title_full_unstemmed An Efficient Local Search Algorithm for the Minimum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Dominating Set Problem
title_sort efficient local search algorithm for the minimum <inline-formula> <tex-math notation="latex">$k$ </tex-math></inline-formula>-dominating set problem
publisher IEEE
publishDate 2018
url https://doaj.org/article/b53fcef925c64cfcba53693c05b54eb1
work_keys_str_mv AT ruizhili anefficientlocalsearchalgorithmfortheminimuminlineformulatexmathnotationlatexktexmathinlineformuladominatingsetproblem
AT huanliu anefficientlocalsearchalgorithmfortheminimuminlineformulatexmathnotationlatexktexmathinlineformuladominatingsetproblem
AT xiaoliwu anefficientlocalsearchalgorithmfortheminimuminlineformulatexmathnotationlatexktexmathinlineformuladominatingsetproblem
AT junwu anefficientlocalsearchalgorithmfortheminimuminlineformulatexmathnotationlatexktexmathinlineformuladominatingsetproblem
AT minghaoyin anefficientlocalsearchalgorithmfortheminimuminlineformulatexmathnotationlatexktexmathinlineformuladominatingsetproblem
AT ruizhili efficientlocalsearchalgorithmfortheminimuminlineformulatexmathnotationlatexktexmathinlineformuladominatingsetproblem
AT huanliu efficientlocalsearchalgorithmfortheminimuminlineformulatexmathnotationlatexktexmathinlineformuladominatingsetproblem
AT xiaoliwu efficientlocalsearchalgorithmfortheminimuminlineformulatexmathnotationlatexktexmathinlineformuladominatingsetproblem
AT junwu efficientlocalsearchalgorithmfortheminimuminlineformulatexmathnotationlatexktexmathinlineformuladominatingsetproblem
AT minghaoyin efficientlocalsearchalgorithmfortheminimuminlineformulatexmathnotationlatexktexmathinlineformuladominatingsetproblem
_version_ 1718420689006886912

Ejemplares similares