TÃtulo | Application of CMSA to the Minimum Capacitated Dominating Set Problem |

Publication Type | Conference Paper |

Year of Publication | 2019 |

Authors | Davidson PPinacho [1], Bouamama S [2], Blum C [3] |

Conference Name | Genetic and Evolutionary Computation Conference (GECCO 2019) |

Editorial | ACM Press |

Conference Location | Prague, Czech Republic |

PaginaciÃ³n | 321-328 |

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

DOI | 10.1145/3321707.3321807 [4] |