Un marco general para el diseño de heurísticas constructivas para problemas de embebidos de grafos

Abstract

Los problemas de embebido de grafos (GLP, por sus siglas en inglés, Graph Layout Problems) son una familia de problemas de optimización combinatoria que buscan asignar los vértices de un grafo de entrada a los vértices de un grafo huésped, satisfaciendo restricciones específicas y optimizando una función matemática. Debido a su complejidad computacional, se suelen utilizar algoritmos aproximados, como las heurísticas. Este artículo presenta una revisión de las heurísticas constructivas que se utilizan para generar soluciones de partida para algunos de los GLP más estudiados de la literatura. A partir de la revisión realizada, se propone un marco general para la propuesta de heurísticas constructivas para esta familia de problemas u otros problemas relacionados, así como un conjunto de posibles trabajos futuros.