Informações:

Publicações do PESC

Título
Geração de Bicliques de Um Grafo
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
19/10/2004
Resumo

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.

Abstract

This work describes a study on the generation of bicliques of a graph. A complete bipartite set B is a subset of vertices admitting a bipartition B = X U Y, such that both X and Y are independent sets, and a11 vertices of X are adjacent to those of Y. If both X, Y # @t,h en B is called proper. A biclique is a maximal proper complete bipartite set of a graph. When the requirement that X and Y are independent sets of G is dropped, we have a non-induced biclique. We show that it is NP-complete to test whether a subset of the vertices of a graph is part of a biclique. We also show that there is no polynomial-time delay algorithm for generating a11 bicliques in reverse lexicographic order, unless P = NP. On the other hand, we describe different polynomial-time delay algorithms for the generation of bicliques of a graph. We present an algorithm that generates a11 bicliques of a graph in lexicographic order. We also describe an algorithm that generates all noninduced bicliques of a graph. In addition, we propose specialized efficient algorithms for generating the bicliques of special classes of graphs.

Topo