Abstract
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
Associate Professor
J. Manuel Colmenar
Full Professor
My research interests are focused on metaheuristics applied to optimization problems. I have worked on different combinatorial optimization problems applying trajectorial algorithms such us GRASP or VNS. Besides, I am very interested in applications of Grammatical Evolution, specifically in model and prediction domain, as alternative to machine learning approaches.
Abraham Duarte
Full Professor
Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.