Encontrando grafos bipartitos completos mediante Busqueda de Vecindad Variable

Abstract

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

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.

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.