Barrakuda: A Hybrid Evolutionary Algorithm for Minimum Capacitated Dominating Set Problem

Pedro Pinacho-Davidson and Christian Blum
Additional contact information
Pedro Pinacho-Davidson: Department of Computer Science, Faculty of Engineering, Universidad de Concepción, Concepción 4070409, Chile
Christian Blum: Artificial Intelligence Research Institute (IIIA-CSIC), Campus of the UAB, 08193 Bellaterra, Spain

Mathematics, 2020, vol. 8, issue 11, 1-26

Abstract: The minimum capacitated dominating set problem is an NP-hard variant of the well-known minimum dominating set problem in undirected graphs. This problem finds applications in the context of clustering and routing in wireless networks. Two algorithms are presented in this work. The first one is an extended version of construct, merge, solve and adapt, while the main contribution is a hybrid between a biased random key genetic algorithm and an exact approach which we labeled Barrakuda . Both algorithms are evaluated on a large set of benchmark instances from the literature. In addition, they are tested on a new, more challenging benchmark set of larger problem instances. In the context of the problem instances from the literature, the performance of our algorithms is very similar. Moreover, both algorithms clearly outperform the best approach from the literature. In contrast, Barrakuda is clearly the best-performing algorithm for the new, more challenging problem instances.

Keywords: minimum capacitated dominating set problem; hybrid evolutionary algorithm; biased random key genetic algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
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/8/11/1858/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/11/1858/ (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:8:y:2020:i:11:p:1858-:d:433634

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