Generating bicliques of a graph in lexicographic order

DOI10.1016/j.tcs.2005.01.014zbMath1076.68048OpenAlexW1979312971MaRDI 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 orderenumerationNP-completenessalgorithmicsbicliquepolynomial-time delay

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs, ⋮ On Independent Sets and Bicliques in Graphs ⋮ Unnamed Item ⋮ On independent sets and bicliques in graphs ⋮ Exact exponential-time algorithms for finding bicliques ⋮ Almost every graph is divergent under the biclique operator ⋮ Bicolored independent sets and bicliques ⋮ Tight lower bounds on the number of bicliques in false-twin-free graphs ⋮ Enumerating maximal bicliques in bipartite graphs with favorable degree sequences ⋮ Maximum Edge Bicliques in Tree Convex Bipartite Graphs ⋮ DECOMPOSITIONAL APPROACH TO RESEARCH OF FORMAL CONTEXTS ⋮ Efficient enumeration of maximal induced bicliques ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ Finding maximum edge bicliques in convex bipartite graphs ⋮ On the Iterated Biclique Operator ⋮ Biclique graphs and biclique matrices ⋮ On Maximal Chain Subgraphs and Covers of Bipartite Graphs ⋮ Enumeration aspects of maximal cliques and bicliques

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

This page was built for publication: Generating bicliques of a graph in lexicographic order