On the generation of bicliques of a graph

DOI10.1016/J.DAM.2007.03.017MaRDI QIDQ5919931zbMATH OpenOpenAlexFDO

Authors Vânia M. F. Dias, Celina M. H. de Figueiredo, Jayme L. 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

algorithmsbicliqueconvex bipartite graphsenumerationNP-completepolynomial time delay

Mathematics Subject Classification ID

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

Recommendations

• Generating bicliques of a graph in lexicographic order
• Clustering minimum biclique completion of a bipartite graph
• Bicliques in graphs. I: Bounds on their number
• Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs
• On independent sets and bicliques in graphs

Cites work

• Absolute reflexive retracts and absolute bipartite retracts
• Algorithm Theory - SWAT 2004
• Approximating Clique and Biclique Problems
• Arboricity and bipartite subgraph listing algorithms
• Bicliques in graphs. I: Bounds on their number
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• Consensus algorithms for the generation of all maximal bicliques
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1107738 (Why is no real title available?)
• Node-and edge-deletion NP-complete problems
• On bipartite and multipartite clique problems
• Perfect Elimination and Chordal Bipartite Graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The maximum edge biclique problem is NP-complete

Cited in

(21)

• Finding maximum edge bicliques in convex bipartite graphs
• Efficient enumeration of maximal induced bicliques
• On bicliques and the second clique graph of suspensions
• Finding and enumerating large intersections
• On independent sets and bicliques in graphs
• Enumerating maximal bicliques in bipartite graphs with favorable degree sequences
• A combinatorial game over biclique-hypergraphs of powers of paths and of powers of cycles through monochromatic transversals
• On maximal chain subgraphs and covers of bipartite graphs
• Generating fixed density bracelets of arbitrary base
• On co-bicliques
• Bicolored independent sets and bicliques
• Generating near‐bipartite bricks
• Maximum Edge Bicliques in Tree Convex Bipartite Graphs
• Problems and invariants connected with bicliques and multicliques of graphs
• Biclique-colouring verification complexity and biclique-colouring power graphs
• On the iterated biclique operator
• Linear-time algorithm for generating c-isolated bicliques
• Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
• On Independent Sets and Bicliques in Graphs
• Generating bicliques of a graph in lexicographic order
• Almost every graph is divergent under the biclique operator

This page was built for publication: On the generation of bicliques of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5919931)