Generating bicliques of a graph in lexicographic order (Q557825): Difference between revisions

A complete bipartite set \(B\) of a graph is a subset of vertices admitting a bipartition \(B=X\cup 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\neq \emptyset\), then \(B\) is called proper. A biclique is a maximal proper complete bipartite set of a graph. The authors present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. They show also that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The paper contains an extension of results of \textit{D. S. Johnson, C. H. Papadimitriou} and \textit{M. Yannakakis} [``On generating all maximal independent sets'', Inf. Process. Lett. 27, 119--123 (1988; Zbl 0654.68086)].