Resumen
Graph layout problems refer to a family of optimization problems with relevant applications in VLSI design, information retrieval, numerical analysis, computational biology, or graph theory. In this paper, we focus on a variant where the graph is mapped over a specific structure referred to as book, which consists of a spine and a number of pages. Vertices of the graph are allocated in the spine, which is usually represented as a line, and edges are assigned to pages of the book, which are represented as half-planes that have the spine as its boundary. The experience shows that one of the main quality desired for layout of graphs is the minimization of edge crossing. The -page crossing number minimization problem (KPMP) aims to reduce as much as possible the number of crossings between edges belonging to the same page. We propose the application of the VNS metaheuristic to efficiently solve the KPMP. Experiments show a remarkable improvement over the state-of-the-art procedures for a large set of instances, leading the proposed VNS algorithm as a promising strategy to solve this family of book drawing problems.
Alberto Herrán González
Profesor Titular de Universidad
J. Manuel Colmenar
Profesor Titular de Universidad
Mis intereses de investigación se centran en las metaheurísticas aplicadas a problemas de optimización. He trabajado en diferentes problemas de optimización combinatoria aplicando algoritmos trajectoriales como GRASP o VNS. Además, estoy muy interesado en las aplicaciones de la Evolución Gramatical, específicamente en el dominio de los modelos y la predicción, como alternativa a los enfoques de aprendizaje automático.
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.