Abstract
Finding minimum dominating sets in graphs is a problem that has been widely studied in the literature. However, due to the increase in the size and complexity of networks, new algorithms with the ability to provide high quality solutions in short computing times are desirable. This work presents a Greedy Randomized Adaptive Search Procedure for dealing with the Minimum Dominating Set Problem in large networks. The algorithm is conformed by an efficient constructive procedure to generate promising initial solutions and a local search designed to find a local optimum with respect to those initial solutions. The experimental results show the competitiveness of the proposed algorithm when comparing it with the state-of-the-art methods.
Alejandra Casado
Artificial Intelligence Phd Student
My research interests include metaheuristics and combinatorial optimization.
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.