Heuristics for the weighted total domination problem

Resumen

El problema de dominación total ponderada (Weighted Total Domination Problem, WTDP) pertenece a la familia de los problemas de dominación sobre grafos. Dado un grafo ponderado por aristas y vértices, el WTDP consiste en seleccionar un conjunto dominante total D, tal que la suma de pesos de vértices y aristas del subgrafo inducido por D mas, para cada vértice que no pertenece a D, el peso mínimo de su arista a un vértice en D sea minimizado. Un conjunto dominante total D es un subconjunto de los vértices del grafo, tal que cada vértice, incluyendo los de D, es al menos adyacente a un vértice en D. Este problema surge en muchas aplicaciones de la vida real estrechamente relacionadas con los problemas de cobertura y de conjuntos independientes; sin embargo, sigue siendo computacionalmente complejo debido a que se trata de problemas NP-difíciles. Este trabajo presenta un Variable Neighborhood Search (VNS) para abordar el WTDP, e investiga las ventajas y desventajas de una estrategia de inicio múltiple dentro de la metodología VNS. Además, desarrollamos un biased greedy randomized adaptive search procedure (Biased GRASP) que sigue añadiendo elementos una vez que se encuentra una solución factible para producir soluciones iniciales de alta calidad. Realizamos un extenso análisis numérico para estudiar las influencias de los componentes algorítmicos y revelar la contribución de los elementos y estrategias de nuestro método. Por último, el análisis empírico muestra que nuestra propuesta supera los resultados del estado del arte, y el análisis estadístico confirma la superioridad de nuestra propuesta para encontrar los mejores conjuntos dominantes totales.

Cita esta publicación

Casado, A., Sánchez-Oro, J. & Martínez-Gavara, A. (2025). Heuristics for the weighted total domination problem. TOP 33, 395–436.