Information

Teachers: Abraham Duarte and Juan José Pantrigo

English title: Metaheuristics applied for graph layout problems

English summary

Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. A linear layout is a labeling of the nodes of a graph with distinct integers. A large amount of relevant problems in different areas can be formulated as graph layout problems. These include network optimization, VLSI circuit design, information retrieval, numerical analysis, computational biology, graph theory, scheduling, archaeology,etc. [J Diaz - Mathematical Foundations of Computer Science 1992]. In this master thesis, we will study and apply several metaheuristics in order to optimize this problem.

Abstract

Los problemas de etiquetado lineal de grafos son un conjunto de problemas en los cuales la meta es conseguir etiquetar cada vértice de un grafo con un número real. Existen varios problemas que siguen este modelo y tienen objetivos diferentes. Por ejemplo, intentar que la suma de las diferencias de etiquetas de los nodos sea la mínima, como es en el caso del problema del Etiquetado Lineal Mínimo. Estos problemas, tratados desde hace décadas siguen teniendo un campo abierto de posibilidades e investigación, en la que se siguen obteniendo técnicas para reducir la complejidad de ejecución y tiempo para darles solución.