|Títol||Application of CMSA to the Minimum Capacitated Dominating Set Problem|
|Publication Type||Conference Paper|
|Year of Publication||2019|
|Authors||Davidson PPinacho, Bouamama S, Blum C|
|Conference Name||Genetic and Evolutionary Computation Conference (GECCO 2019)|
|Conference Location||Prague, Czech Republic|
This work deals with the so-called minimum capacitated dominating set (CAPMDS) problem, which is an NP-Hard combinatorial optimization problem in graphs. In this paper we describe the application of a recently introduced hybrid algorithm known as Construct, Merge, Solve \& Adapt (CMSA) to this problem. Moreover, we evaluate the performance of a standalone ILP solver. The results show that both CMSA and the ILP solver outperform current state-of-the-art algorithms from the literature. Moreover, in contrast to the ILP solver, the performance of CMSA does not degrade for the largest problem instances. The experimental evaluation is based on a benchmark dataset containing two different graph topologies and considering graphs with variable and uniform node capacities.
- Quant a IIIA