Resumen
The term layout problem comes from the context of Very Large-Scale Integration (VLSI) circuit design. Graph layouts are optimization problems where the main objective is to project an original graph into a predefined host graph, usually a horizontal line. In this paper, some of the most relevant linear layout problems are reviewed, where the purpose is to minimize the objective function: the Cutwidth, the Minimum Linear Arrangement, the Vertex Separation, the SumCut, and the Bandwidth. Each problem is presented with its formal definition and it is illustrated with a detailed example. Additionally, the most relevant heuristic methods in the associated literature are reviewed together with the instances used in their evaluation. Since linear layouts represent a challenge for optimization methods in general and, for heuristics in particular, this review pays special attention to the strategies and methodologies which provide high-quality solutions.
Eduardo García Pardo
Catedrático de Universidad
Miembro fundador del grupo de investigación GRAFO, cuya línea de investigación principal es el desarrollo de algoritmos para abordar problemas de optimización, temática sobre la que versa la Tesis Doctoral del investigador y en la que se enmarcan sus publicaciones más destacadas.
Abraham Duarte
Catedrático de Universidad
Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.