Tesis doctorales de la Escuela Internacional de Doctorado de la URJC desde el curso 2024/25
Nuevos enfoques metaheurísticos para resolver problemas de dominación
Autor
CASADO CEBALLOS, ALEJANDRA
Director
DUARTE MUÑOZ, ABRAHAM
Codirector
PÉREZ PELÓ, SERGIO
Fecha de depósito
09-07-2025
Periodo de exposición pública
9 a 23 de julio de 2025
Fecha de defensa
Sin especificar
Modalidad
Presencial
Programa
Tecnologías de la información y las Comunicaciones (TICs)
Mención internacional
No
Resumen
En el contexto actual, donde los sistemas complejos, modelados normalmente como redes, son esenciales para numerosas actividades humanas, resulta crucial identificar rápidamente elementos clave dentro de redes de gran tamaño. Los problemas de dominación en grafos modelan situaciones en las que se debe seleccionar un subconjunto mínimo de nodos estratégicos que cubran eficientemente al resto de la red. Este tipo de problemas es relevante en aplicaciones como el despliegue de infraestructuras de telecomunicaciones, redes de sensores, campañas de vacunación o la detección de vulnerabilidades en sistemas informáticos. Resolverlos con eficacia tiene un efecto directo en la eficiencia operativa, la reducción de costes y la resiliencia de los sistemas.
Sin embargo, su exigencia computacional, especialmente en variantes complejas, limita el uso de algoritmos exactos en escenarios de gran escala debido al crecimiento exponencial del espacio de búsqueda. Aunque estos métodos garantizan soluciones óptimas, sus altos tiempos de cómputo restringen su aplicabilidad práctica. En contraste, los algoritmos heurísticos permiten explorar el espacio de soluciones de manera eficiente, ofreciendo resultados de alta calidad en tiempos razonables, aunque sin asegurar optimalidad global.
Las heurísticas son especialmente valiosas en contextos dinámicos o con recursos limitados, y su flexibilidad permite adaptarse a distintas variantes del problema, considerando múltiples restricciones y objetivos. Así, el desarrollo de métodos heurísticos eficaces para problemas de dominación representa tanto un avance metodológico como una aportación práctica relevante en múltiples dominios donde la toma de decisiones basada en grafos es esencial.
El Problema de Dominación en Grafos, un problema NP-difícil, consiste en identificar un subconjunto mínimo de nodos tal que todos los nodos del grafo estén en él o sean adyacentes a alguno de los elementos de ese subconjunto. Sus aplicaciones incluyen la colocación de sensores, el diseño de redes de vigilancia o la optimización de campañas sanitarias. Entre sus variantes destacan la dominación total, la dominación conexa y la dominación ponderada, que introducen distintas restricciones y objetivos según el contexto.
Estas variantes pueden modelarse como problemas de optimización, donde el objetivo común es lograr configuraciones eficientes que garanticen una cobertura efectiva del grafo, minimizando el número de nodos dominantes u optimizando otros criterios como coste o robustez.
En esta Tesis Doctoral se proponen diversos algoritmos heurísticos para resolver varias versiones del Problema de Dominación en Grafos. Se han empleado técnicas como Variable Neighborhood Search, Iterated Greedy y Scatter Search, evaluadas sobre instancias sintéticas y reales, obteniendo soluciones competitivas frente a los métodos del estado del arte.
