Resumen
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
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.
Jesús Sánchez-Oro
Profesor Titular de Universidad
Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.