MATHEURISTICS FOR VARIANTS OF THE DOMINATING SET PROBLEM
Mayra Carvalho Albuquerque · 2018
This thesis addresses the Dominating Set Problem, an NPhard problem with great relevance in applications related to wireless network design, data mining, coding theory, among others.The minimum dominating set in a graph is a minimal set of vertices so that each vertex of the graph belongs to it or is adjacent to a vertex of this set.We study three variants of the problem: first, in the presence of weights on vertices, searching for a dominating set with smallest total weight; second, a variant where the subgraph induced by the dominating set needs to be connected, and, finally, the variant that encompasses these two characteristics.To solve these three problems, we propose a hybrid algorithm based on tabu search with additional mathematical-programming components, leading to a method sometimes called "matheuristic".Several additional techniques and large neighborhoods are also employed to reach promising regions in the search space.Our experimental analyses show the good contribution of all these individual components.Finally, the algorithm is tested on the covering code problem, which can be viewed as a special case of the minimum dominating set problem.The codes are studied for the Hamming metric and the Rosenbloom-Tsfasman metric.For this last case, several shorter codes were found.