Abstract
The graph bandwidth minimization problem is an interesting problem that has become relevant in a wide range of domains. Networks communication, VLSI layout designs, parallel algorithms simulations, matrix decomposition, are some of which areas where the reduction of the bandwidth is very significant. The problem consists of embedding a graph G into a line with the aim of minimizing the maximum distance between adjacent vertices. In this paper, we are focused on the 2D bandwidth minimization variant, which considers embedding the graph in a two-dimensional grid instead of in a line. Specifically, we study the problem deeply analyzing its complexity and considering a survey of different approximate algorithms for graphs. The review concludes outlining the conceptual basis of the heuristic technique that we plan to apply to this graph problem.
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.
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.