On the generation of bicliques of a graph |
| |
Authors: | Vâ nia M.F. Dias,Celina M.H. de Figueiredo,Jayme L. Szwarcfiter |
| |
Affiliation: | a COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, 21945-970 Rio de Janeiro, Brazil b IM and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, 21945-970 Rio de Janeiro, Brazil c IM, COPPE, and NCE, Universidade Federal do Rio de Janeiro, Caixa Postal 68511, 21945-970 Rio de Janeiro, Brazil |
| |
Abstract: | An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X∪Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y≠∅, then 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 propose 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. |
| |
Keywords: | Algorithms Biclique Enumeration NP-complete Polynomial time delay Convex bipartite graphs |
本文献已被 ScienceDirect 等数据库收录! |
|