Abstract
El problema de dominación total de grafos ponderados consiste en determinar un conjunto de dominación total D en un grafo cuyos vértices y aristas tienen pesos asociados, de forma que se minimice el coste total. Este coste se define como la suma de los pesos de los vértices incluidos en D, los pesos de las aristas del subgrafo inducido por D, y, para cada vértice no seleccionado, el peso mínimo de la conexión con algún vértice de D. Este problema, considerado NP-duro por su dificultad, tiene aplicaciones en redes de comunicación, localización de instalaciones y redes sociales, entre otras. El artículo que aquí se presenta y publicado en [2 ], propone una metodología basada en una búsqueda de vecindades variables (VNS) y en una construcción adaptativa mediante Biased GRASP, lo que permite obtener soluciones de alta calidad en instancias de gran tamaño.
Alejandra Casado
Phd in Artificial Intelligence
My research interests include metaheuristics and combinatorial optimization.