E. García Pardo, S. Cavero, A. Duarte
Algunos problemas de optimización necesitan ser modelados mediante grafos para abordarlos computacionalmente. Entre estos problemas se encuentran los problemas de ordenación o etiquetado de grafos cuyo objetivo es optimizar una función objetivo cuando se realiza una proyección de los vértices de un grafo de entrada en los vértices de un grafo huésped. Los problemas de esta familia con mayor interés son aquellos cuyo grafo huésped es regular. Esta investigación se centra en el estudio de tres problemas cuyo grafo huésped es un grafo ciclo: Cyclic Cutwidth Problem, Cyclic Antibandwidth Problem y Cyclic Bandwidth Problem. Estos problemas pertenecen a la clase NP-Difícil y, por lo tanto, su resolución exacta requiere tiempos de cómputo inasumibles cuando el tamaño del grafo de entrada es grande. Por esta razón, la investigación realizada aborda estos problemas de manera aproximada, mediante técnicas heurísticas y metaheurísticas, alcanzando soluciones de calidad en un tiempo reducido.
Palabras clave: Graph Layout Problems, Embebidos circulares, Heurísticas, Metaheurísticas
Programado
GT09 Heurísticas I. Heurísticas y metaheurísticas
8 de junio de 2022 16:00
A04
