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 NP N P -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.
heuristic dominating set genetic algorithm ant-colony optimization constrained optimization