Resumen de Conjuntos k-dominantes mínimos en grafos ponderados

Ana Dolores López Sánchez , Eva Barrena, Sergio Bermudo Navarrete , Alfredo G. Hernández-Díaz , José Antonio Zamudio Amaya

• En el artículo [1] recientemente publicado proponemos una generalización del conjunto k-dominante en un grafo, cuando consideramos un grafo ponderado.

  Dado un grafo con pesos en sus aristas, un conjunto de vértices es un conjunto k−dominante en un grafo ponderado si para cada vértice fuera del conjunto, la suma de los pesos desde él a los vértices en el conjunto es mayor o igual que k. El número k-dominación en un grafo ponderado es la cardinalidad mínima entre todos los conjuntos k-dominantes en un grafo ponderado. Dado que el problema de encontrar el número k-dominación en un grafo ponderado es N P- difícil, se han comparado dieciséis variantes de un algoritmo exacto Iterated Greedy.

  Los resultados computacionales muestran que la propuesta es capaz de encontrar soluciones óptimas o casi óptimas en un tiempo computacional pequeño.