Empacotamento de bicliques em grafos bipartidos / Biclique packing in bipartite graphs
AUTOR(ES)
Alexandre da Silva Freire
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
02/10/2012
RESUMO
Nesta tese, estudamos o problema de Empacotamento de Bicliques. Um biclique é um grafo bipartido completo. No problema de Empacotamento de Bicliques são dados um inteiro k e um grafo bipartido G e deseja-se encontrar um conjunto de k bicliques, subgrafos de G, dois a dois disjuntos nos vértices, tal que a quantidade total de arestas dos bicliques escolhidos seja máxima. No caso em que k=1, temos o problema de Biclique máximo. Esses dois problemas possuem aplicações na área de Bioinformática. Mantemos neste trabalho um enfoque prático, no sentido de que nosso interesse é resolver instâncias desses dois problemas com tamanho razoavelmente grande. Para isso, utilizamos técnicas de Programação Linear Inteira. Para avaliar os métodos propostos aqui, mostramos resultados de experimentos computacionais feitos com instâncias vindas de aplicações e também com instâncias geradas aleatoriamente.
ASSUNTO(S)
biclique máximo biclique packing column generation empacotamento de bicliques geração de colunas integer programming maximum biclique programação inteira
