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.pdfCaso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web