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.

Publication
XVIII Conferencia de la Asociación Española para la Inteligencia Artificial (CAEPIA 2018) 23-26 de octubre de 2018 Granada, España
Jesús Sánchez-Oro
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
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.