Resumen
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
Estudiante de Doctorado en Inteligencia Artificial
Mi investigación se centra en el uso de metaheuristicas y la resolución de problemas de optimización combinatoria.
Jesús Sánchez-Oro
Profesor Titular de Universidad
Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.