L. Cruz Pérez, A. D. López Sánchez, E. Barrena Algara, A. García Hernández-Díaz
El Distance based Dominating Set Problem (DDSP) es una variante del problema clásico de dominación en grafos en el que se consideran grafos ponderados donde los pesos de las aristas representan distancias. Se trata de un problema de optimización biobjetivo que busca minimizar tanto el tamaño del conjunto dominante como la distancia del nodo más alejado a dicho conjunto. A lo largo del trabajo se propone, analiza y resuelve el DDSP mediante un método metaheurístico. En particular, se plantea la implementación de un algoritmo basado en GRASP y se evalúa su desempeño en distintos tipos de grafos.
Palabras clave: Dominación en grafos, optimización biobjetivo, metahuerística, GRASP
Programado
Heurísticas y Metaheurísticas III
10 de junio de 2025 19:00
MR 1