Hybrid metaheuristic algorithms for minimum weight dominating set

Minimum weight dominating set (MWDS) finds many uses in solving problems as varied as clustering in wireless networks, multi-document summarization in information retrieval and so on. It is proven to be NPNP-hard, even for unit disk graphs. Many centralized and distributed, greedy and approximation algorithms have been proposed for the MWDS problem. However, all the approximation algorithms are limited to unit disk graphs which are primarily used to model wireless networks. This assumption fails when applied to other domains. In this paper, we present two metaheuristic algorithms – a hybrid genetic algorithm and a hybrid ant colony optimization algorithm – for the problem of computing minimum weight dominating set. We compare our results with that of a greedy heuristic as well as the only other metaheuristic algorithm proposed so far in the literature and show that our algorithms are far better than these algorithms.

Graphical abstractMinimum weight dominating set (MWDS) of the given graph comprises of nodes 2, 0, 1, and 6 for a total weight of 347. Figure optionsDownload full-size imageDownload as PowerPoint slideHighlights► The HGA is a steady-state genetic algorithm that uses binary tournament with a simple bit-flip mutation scheme. ► The ACO algorithm uses only the pheromone deposit on the nodes to determine the next node to be visited by the ant. ► Addition of a pre-processing step to the ACO reduces time but does not improve the quality of the solution. ► For both HGA and ACO algorithms, a minimization heuristic is added as the local search component to reduce the weight of the generated population member. ► Both our proposed algorithms perform better than the only metaheuristic solution in the literature for this problem.