Application of CMSA to the minimum capacitated dominating set problem

Abstract

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.