On the generation of bicliques of a graph

DOI10.1016/j.dam.2007.03.017zbMath1126.05074OpenAlexW2033462054MaRDI QIDQ5919931

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

Publication date: 19 September 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.03.017

zbMATH Keywords

algorithmsenumerationNP-completebicliqueconvex bipartite graphspolynomial time delay

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On Independent Sets and Bicliques in Graphs ⋮ Unnamed Item ⋮ On independent sets and bicliques in graphs ⋮ Almost every graph is divergent under the biclique operator ⋮ Bicolored independent sets and bicliques ⋮ A combinatorial game over biclique-hypergraphs of powers of paths and of powers of cycles through monochromatic transversals ⋮ Enumerating maximal bicliques in bipartite graphs with favorable degree sequences ⋮ Maximum Edge Bicliques in Tree Convex Bipartite Graphs ⋮ Biclique-colouring verification complexity and biclique-colouring power graphs ⋮ 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 ⋮ On Maximal Chain Subgraphs and Covers of Bipartite Graphs ⋮ Linear-time algorithm for generating c-isolated bicliques ⋮ Finding and enumerating large intersections ⋮ Generating fixed density bracelets of arbitrary base

Cites Work

• Unnamed Item
• Unnamed Item
• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• 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
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Arboricity and bipartite subgraph listing algorithms
• The maximum edge biclique problem is NP-complete
• On Bipartite and Multipartite Clique Problems
• Perfect Elimination and Chordal Bipartite Graphs
• Approximating Clique and Biclique Problems
• Algorithm Theory - SWAT 2004
• Node-and edge-deletion NP-complete problems
• Bicliques in graphs. I: Bounds on their number