Vânia Maria Félix Dias,  Celina M. H. de Figueiredo,  Jayme L. Szwarcfiter. 

This work describes a study on the generation of bicliques of a graph. 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 all 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 all bicliques of a graph in lexicographic order. We also describe an algorithm that generates all non-induced bicliques of a graph. In addition, we propose specialized efficient algorithms for generating the bicliques of special classes of graphs.

http://www.lbd.dcc.ufmg.br/colecoes/ctd/2005/010.pdf

Processando consulta.