A Novel Hybrid Algorithm for Minimum Total Dominating Set Problem

Fuyu Yuan, Chenxi Li, Xin Gao, Minghao Yin and Yiyuan Wang
Additional contact information
Fuyu Yuan: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130000, China
Chenxi Li: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130000, China
Xin Gao: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130000, China
Minghao Yin: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130000, China
Yiyuan Wang: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130000, China

Mathematics, 2019, vol. 7, issue 3, 1-11

Abstract: The minimum total dominating set (MTDS) problem is a variant of the classical dominating set problem. In this paper, we propose a hybrid evolutionary algorithm, which combines local search and genetic algorithm to solve MTDS. Firstly, a novel scoring heuristic is implemented to increase the searching effectiveness and thus get better solutions. Specially, a population including several initial solutions is created first to make the algorithm search more regions and then the local search phase further improves the initial solutions by swapping vertices effectively. Secondly, the repair-based crossover operation creates new solutions to make the algorithm search more feasible regions. Experiments on the classical benchmark DIMACS are carried out to test the performance of the proposed algorithm, and the experimental results show that our algorithm performs much better than its competitor on all instances.

Keywords: minimum total dominating set; evolutionary algorithm; genetic algorithm; local search (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/3/222/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/3/222/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:3:p:222-:d:209600

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().