M. Robles Rodríguez, S. Cavero Díaz, E. G. Pardo
El problema de Minimum Sitting Arrangement (MinSA) es un problema de optimización en el cual el objetivo es embeber un grafo con signos en un grafo huésped no dirigido con una forma regular, de forma que cada vértice del grafo con signos tenga un vértice del grafo huésped asignado. El criterio para asignar los vértices del grafo con signos es minimizar la función objetivo que contabiliza el número de errores del embebido. Más concretamente, en este problema, un error se define como cada uno de los adyacentes negativos situados más cerca que un adyacente positivo. El MinSA ha sido tratado anteriormente en un grafo huésped tipo camino, y ha sido recientemente adaptado a un grafo huésped tipo ciclo. El objetivo es realizar una propuesta basada en algoritmos heurísticos y metaheurísticos para resolver el problema de MinSA para el grafo huésped ciclo.
Palabras clave: Embebido de grafos, MinSA, GRASP, VND
Programado
GT10.HEUR3 Sesión Invitada
8 de noviembre de 2023 17:20
CC3: Sala 1