Multi-Start Local Search Algorithm for the Minimum Connected Dominating Set Problems

Ruizhi Li, Shuli Hu, Huan Liu, Ruiting Li, Dantong Ouyang and Minghao Yin
Additional contact information
Ruizhi Li: School of Computer Science and Technology, Jilin University, Changchun 130012, China
Shuli Hu: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130024, China
Huan Liu: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130024, China
Ruiting Li: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130024, China
Dantong Ouyang: School of Computer Science and Technology, Jilin University, Changchun 130012, China
Minghao Yin: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130024, China

Mathematics, 2019, vol. 7, issue 12, 1-14

Abstract: The minimum connected dominating set (MCDS) problem is a very significant NP-hard combinatorial optimization problem, and it has been used in many fields such as wireless sensor networks and ad hoc networks. In this paper, we propose a novel multi-start local search algorithm (MSLS) to tackle the minimum connected dominating set problem. Firstly, we present the fitness mechanism to design the vertex score mechanism so that our algorithm can jump out of the local optimum. Secondly, we use the configuration checking (CC) mechanism to avoid the cycling problem. Then, we propose the vertex flipping mechanism to change the vertex state by combing the CC mechanism with the vertex score mechanism. Finally, we propose a multi-start local search framework based on these mechanisms. We compare the algorithm MSLS with other compared algorithms on extensive instances. The results of experiment show that MSLS is superior to other algorithms in solution quality and time efficiency on most instances.

Keywords: minimum connected dominating set; configuration checking; vertex score mechanism; multi-start local search (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/12/1173/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/12/1173/ (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:12:p:1173-:d:293555

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