BDBComp
Parceria:
SBC
Geração ao Bicliques de um Grafo

Vânia Maria Félix DiasCelina M. H. de FigueiredoJayme 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

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br
     Mantida por:
LBD