Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/43970
Title in Portuguese: Algoritmos exatos para o problema da biclique induzida balanceada máxima
Author: Melo, Marcus Vinicius Martins
Advisor(s): Dantas, Rennan Ferreira
Co-advisor(s): Viana, Luiz Alberto do Carmo
Keywords: Biclique Balanceada Máxima
Bonecas Russas
Partições em Cliques
Branch and Bound
Issue Date: 2019
Citation: MELO, Marcus Vinicius Martins. Algoritmos exatos para o problema da biclique induzida balanceada máxima. 2019. 50 f. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Campus de Crateús, Universidade Federal do Ceará, Crateús, 2019.
Abstract in Portuguese: O presente trabalho apresenta dois algoritmos Branch and Bound (B&B) para o Problema da Biclique Induzida Balanceada Máxima (PBIBM). Ambos os algoritmos combinam de forma eficiente técnicas já empregadas com sucesso na literatura para resolver o problema. O primeiro algoritmo, denominado ALGBRPC, combina as técnicas de Partições em Cliques e Bonecas Russas. A estratégia do algoritmo é utilizar Partições em Cliques para podar os subproblemas gerados por cada boneca. O segundo algoritmo, denominado ALGBRUBP, combina a técnica de Bonecas Russas com um procedimento de Upper Bound Propagation (UBP). Este algoritmo foi desenvolvido especificamente para a classe de grafos bipartidos, visto que Partições em Cliques é ineficaz para esta classe. Por fim, testes computacionais foram realizados comparando os dois algoritmos propostos com os algoritmos base, utilizando conjuntos de instâncias disponíveis na literatura e de grafos gerados de forma aleatória. O primeiro algoritmo supera o algoritmo base na grande maioria das instâncias, tanto no número de subproblemas quanto no tempo computacionaldemandado. Osegundoalgoritmosuperaoalgoritmobaseemalgumasinstâncias de grafos bipartidos.
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.
URI: http://www.repositorio.ufc.br/handle/riufc/43970
metadata.dc.type: TCC
Appears in Collections:CIÊNCIA DA COMPUTAÇÃO - CRATEÚS - Monografias

Files in This Item:
File Description SizeFormat 
2019_tcc_mvmmelo.pdf454,37 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.