Resumen
In the last few decades, graph domination problems have attracted the attention of both academics and practitioners. In these problems, a subset of vertices is selected such that every vertex in the graph is either in the subset or adjacent to at least one selected vertex. One of the most extended variants is the Roman Domination Problem (RDP), where vertices are assigned values to ensure coverage under specific protection rules. This research addresses the Double Roman Domination Problem (DROMDP), a more restrictive extension of RDP in which stronger domination conditions are imposed to guarantee coverage even under potential vertex failures. In this paper, an algorithm based on the Iterated Local Search (ILS) framework is proposed, considering the use of two constructive procedures, two local search methods, and two perturbation mechanisms to find high-quality solutions. The results obtained are compared with the state-of-the-art method, based on Ant Colony Optimization, with ILS emerging as the most competitive algorithm for DROMDP.
Alejandra Casado
Doctora 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.