METAHEURÍSTICAS PARA EL MINIMUM WEIGHTED DOMINATING SET PROBLEM

Abstract

El mínimo conjunto dominante de un grafo se compone del menor número de nodos que, o bien pertenecen a este subconjunto, o bien son adyacentes a alguno de los nodos que lo forma. Este Trabajo de Fin de Grado (TFG) propone un algoritmo para la resolución del problema Minimum Weighted Dominating Set, variante del problema anterior en el que a cada uno de los nodos le corresponde un peso determinado, y en el que se debe seleccionar el mínimo conjunto dominante de menor peso, aprovechando las ventajas de las metaheurísticas Greedy Randomized Adaptive Search Procedure (GRASP) e Iterated Greedy(IG).