zbMATH — the first resource for mathematics

Generating bicliques of a graph in lexicographic order. (English) Zbl 1076.68048
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 D. S. Johnson, C. H. Papadimitriou and M. Yannakakis [“On generating all maximal independent sets”, Inf. Process. Lett. 27, 119–123 (1988; Zbl 0654.68086)].

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] G. Alexe, S. Alexe, Y. Crama, S. Foldes, P. Hammer, B. Simeone, Consensus algorithms for the generation of all maximal bicliques, Discrete Appl. Math. 145 (1) (2004) 11-21. · Zbl 1056.05132
[2] Amilhastre, J.; Vilarem, M.C.; Janssen, P., Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs, Discrete appl. math., 86, 2-3, 125-144, (1998) · Zbl 0906.05067
[3] Bandelt, H.-J.; Farber, M.; Hell, P., Absolute reflexive retracts and absolute bipartite retracts, Discrete appl. math., 44, 1-3, 9-20, (1993) · Zbl 0795.05133
[4] Dawande, M.; Keskinocak, P.; Swaminathan, J.M.; Tayur, S., On bipartite and multipartite clique problems, J. algorithms, 41, 2, 388-403, (2001) · Zbl 1017.68088
[5] Garey, M.; Johnson, D., Computers and intractability, a guide to the theory of NP-completeness, (1979), W.H. Freeman and Company New York · Zbl 0411.68039
[6] Golumbic, M.C.; Goss, C.F., Perfect elimination and chordal bipartite graphs, J. graph theory, 2, 2, 155-163, (1978) · Zbl 0411.05060
[7] Hochbaum, D.S., Approximating clique and biclique problems, J. algorithms, 29, 1, 174-200, (1998) · Zbl 0919.68056
[8] Johnson, D.S.; Yannakakis, M.; Papadimitriou, C.H., On generating all maximal independent sets, Inform. process. lett., 27, 3, 119-123, (1988) · Zbl 0654.68086
[9] Kumar, R.; Raghavan, P.; Rajagopalan, S.; Tomkins, A., Trawling the web for emerging cyber communities, (), 1481-1493
[10] Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Generating all maximal independent setsnp-hardness and polynomial-time algorithms, SIAM J. comput., 9, 3, 558-565, (1980) · Zbl 0445.68054
[11] Müller, H., On edge perfectness and classes of bipartite graphs, Discrete math., 149, 1-3, 159-187, (1996) · Zbl 0844.68095
[12] Orlin, J., Containment in graph theorycovering graphs with cliques, Nederl. akad. wetensch. indag. math., 39, 211-218, (1997)
[13] Paull, M.C.; Unger, S.H., Minimizing the number of states in incompletely specified sequential switching functions, IRE trans. electron. comput., EC-8, 356-367, (1959)
[14] Peeters, R., The maximum edge biclique problem is NP-complete, Discrete appl. math., 131, 3, 651-654, (2003) · Zbl 1026.68068
[15] Prisner, E., Bicliques in graphs. II. recognizing \(k\)-path graphs and underlying graphs of line digraphs, (), 273-287 · Zbl 0895.68103
[16] Prisner, E., Bicliques in graphs. I. bounds on their number, Combinatorica, 20, 1, 109-117, (2000) · Zbl 0980.05033
[17] Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all the maximal independent sets, SIAM J. comput., 6, 3, 505-517, (1977) · Zbl 0364.05027
[18] Tuza, Z., Covering of graphs by complete bipartite subgraphscomplexity of 0-1 matrices, Combinatorica, 4, 1, 111-116, (1984) · Zbl 0559.05050
[19] Yannakakis, M., Node- and edge-deletion NP-complete problems, (), 253-264 · Zbl 1282.68131
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.