Geração de Bicliques de Um Grafo

Este trabalho consiste de um estudo sobre a geração de bicliques de um grafo. Um conjunto bipartido completo B é um subconjunto de vértices que admite uma bipartição B = X U Y, tal que X e Y são ambos conjuntos independentes, e todo vértice de X é adjacente a todo vértice de Y. Se X,Y # 0, então dizemos que B é próprio. Uma biclique é um conjunto bipartido completo próprio maximal de um grafo. Se X ou Y não são conjuntos independentes de G, dizemos que B é uma biclique não induzida. Demonstramos que é NP-completo decidir se um subconjunto de vértices de um grafo é parte de uma biclique. Demonstramos também que não existe algoritmo com atraso polinomial para a geração de todas as bicliques em ordem lexicográfica reversa, a menos que P = NP. Por outro lado, descrevemos diferentes algoritmos, todos com atraso polinomial, para a geração das bicliques de um grafo. Apresentamos um algoritmo que gera todas as bicliques em ordem lexicográfica. Também descrevemos um algoritmo que gera todas as bicliques não induzidas de um grafo. Além disso, propomos algoritmos eficientes para a geração de bicliques de classes especiais de grafos.