Algoritmos exatos para o problema da biclique induzida balanceada máxima

Abstract

ThepresentworkintroducetwoBranchandBound(B&B)algorithmsfortheMaximumBalanced Induced Biclique Problem (PBIBM). Both algorithms efficiently combine techniques already successfully used in the literature to solve the problem. The first algorithm, called ALGBRPC, combines the techniques of Clique Cover and Russian Dolls. The strategy of the algorithm is to use Clique Cover to prune subproblems generated by each doll. The second algorithm, called ALGBRUBP, combines the tecniques of Russian Dolls and Upper Bound Propagation (UBP). This algorithm was developed specifically for the bipartite class of graphs, since Clique Cover is ineffective for this class. Finally, computational tests were performed comparing the two proposed algorithms with the base algorithms, using sets of instances available in the literature and randomly generated graphs. The first algorithm outperforms the base algorithm in the vast majority of instances, both in terms of the number of subproblems or in terms of computational time demanded. The second algorithm outperforms the base algorithm in some instances of bipartite graphs.