Resumen de Biased GRASP con VNS para el problema de dominación total de grafos ponderados

Anna Martínez Gavara , Alejandra Casado, Jesús Sánchez Oro Calvo

• 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.