Encontrando grafos bipartitos completos mediante Busqueda de Vecindad Variable

Resumen

El Problema del Maximo Biclique Balanceado, o Maximum Balanced Biclique Problem (MBBP), consiste ennencontrar el biclique de tamano máximo inducido por un grafo bipartito no completo. Se tiene la restriccion adicional de que tanto el tamano del grafo de partida como el biclique inducido tienen el mismo numero de vértices en cada una de sus capas, por lo tanto se dice que son balanceados. Algunas de sus aplicaciones se dan en el diseno de circuitos en integracion a gran escala (VLSI) o el diseno de sistemas nanoelectrónicos, entre otras. Se ha demostrado que este problema de optimizacion combinatoria es NP-Duro. En la literatura se han propuesto diversas heurísticas para solucionarlo, generalmente basadas en la eliminacion de vertices, y más recientemente se ha propuesto un algoritmo evolutivo que tiene los mejores resultados en la literatura. En este trabajo se propone el uso de la metodologıa RVNS para abordar este problema. Esta eleccion se justifica en la díficultad para disenar una búsqueda local efectiva para este problema.

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.

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.