Generating bicliques of a graph in lexicographic order

DOI10.1016/j.tcs.2005.01.014zbMath1076.68048MaRDI QIDQ557825

Vânia M. F. Dias, Jayme Luiz Szwarcfiter, Celina M. Herrera de Figueiredo

Publication date: 30 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.01.014

zbMATH Keywords

lexicographic order; enumeration; NP-completeness; algorithmics; biclique; polynomial-time delay

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

On Independent Sets and Bicliques in Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Absolute reflexive retracts and absolute bipartite retracts
• Consensus algorithms for the generation of all maximal bicliques
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• On generating all maximal independent sets
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• The maximum edge biclique problem is NP-complete
• On edge perfectness and classes of bipartite graphs
• On Bipartite and Multipartite Clique Problems
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• Perfect Elimination and Chordal Bipartite Graphs
• Approximating Clique and Biclique Problems
• Node-and edge-deletion NP-complete problems
• Bicliques in graphs. I: Bounds on their number