J. F. Correcher, M. Landete, J. Peiró, H. Yaman
Dado un grafo no dirigido, el problema del cubrimiento de aristas por vértices generalizado consiste en seleccionar vértices, de manera que cuando un vértice es seleccionado decimos que sus aristas incidentes quedan cubiertas. Cada vértice tiene un coste por ser seleccionado y cada arista conlleva un cierto coste si no queda cubierta, de forma que el objetivo es minimizar el coste total. En esta ponencia presentaremos nuevos resultados sobre fijación de variables y algoritmos de descomposición para abordar dicho problema de un modo más eficiente que con los métodos clásicos. Asimismo, compararemos el rendimiento de los métodos propuestos frente a los clásicos en diversos experimentos computacionales y sugeriremos posibles mejoras de los algoritmos. Finalmente, comentaremos nuevos enfoques en los que ya estamos trabajando y otros que exploraremos en el futuro.
Keywords: generalized vertex cover problem, edge covering, graph decomposition, exact algorithm, monitor placement
Scheduled
Location
June 11, 2025 10:30 AM
Mr 2