Problema de dominación en grafos con distancias
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