TY  - JOUR
AU  - Dias, Vânia M.F.
AU  - de Figueiredo, Celina M.H.
AU  - Szwarcfiter, Jayme L.
T1  - Generating bicliques of a graph in lexicographic order
JO  - Theoretical Computer Science
PY  - 2005/
VL  - 337
IS  - 1-3
SP  - 240 
EP  -  248
UR  - http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280
M3  - DOI: 10.1016/j.tcs.2005.01.014
KW  - graph
KW  - conp
KW  - theory
KW  - set
KW  - independent
L1  - 
SN  - 
N1  - 
N1  - 
AB  - 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[union or logical sum]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[not equal to][empty set], then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. We present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. We also show that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The methods are based on those by Johnson, Papadimitriou and Yannakakis, in the solution of these two problems for independent sets, instead of bicliques.
ER  -