Conjuntos k-dominantes mínimos en grafos ponderados

• Autores: Ana Dolores López Sánchez , Eva Barrena, Sergio Bermudo Navarrete , Alfredo G. Hernández-Díaz , José Antonio Zamudio Amaya
• Localización: Actas del XVI Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados: (MAEB 2025) 28-30 de mayo, Donostia/San Sebastián / coord. por Leticia Hernando Rodríguez , Josu Ceberio Uribe , Jon Vadillo Jueguen, 2025, ISBN 978-84-1319-656-5, págs. 336-339
• Idioma: español
• Enlaces
  • Texto Completo Libro
• Resumen

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