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.
Description
ScienceDirect - Theoretical Computer Science : Generating bicliques of a graph in lexicographic order
%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
%R DOI: 10.1016/j.tcs.2005.01.014
%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.
@article{Dias2005240,
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[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.},
added-at = {2009-02-17T15:55:07.000+0100},
author = {Dias, Vânia M.F. and de Figueiredo, Celina M.H. and Szwarcfiter, Jayme L.},
biburl = {https://www.bibsonomy.org/bibtex/2a60e9536a13fe8f8250b9dac4005130d/folke},
description = {ScienceDirect - Theoretical Computer Science : Generating bicliques of a graph in lexicographic order},
doi = {DOI: 10.1016/j.tcs.2005.01.014},
interhash = {db3c1613d7356478877463a22cecedd4},
intrahash = {a60e9536a13fe8f8250b9dac4005130d},
issn = {0304-3975},
journal = {Theoretical Computer Science},
keywords = {conp graph independent set theory},
number = {1-3},
pages = {240 - 248},
timestamp = {2009-02-17T15:55:07.000+0100},
title = {Generating bicliques of a graph in lexicographic order},
url = {http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280},
volume = 337,
year = 2005
}