%0 Journal Article %1 Dias2005240 %A Dias, VĂ¢nia M.F. %A de Figueiredo, Celina M.H. %A Szwarcfiter, Jayme L. %D 2005 %J Theoretical Computer Science %K conp graph independent set theory %N 1-3 %P 240 - 248 %T Generating bicliques of a graph in lexicographic order %U http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280 %V 337 %X 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=Xunion or logical sumY, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Ynot equal toempty 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.