Exact exponential-time algorithms for finding bicliques

DOI10.1016/j.ipl.2010.10.020zbMath1259.05160OpenAlexW2136829801MaRDI QIDQ1944039

Henning Fernau, Daniel Binkele-Raible, Serge Gaspers, Mathieu Liedloff

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.10.020

zbMATH Keywords

bicliquesgraph algorithmsNP-hard problemexact exponential-time algorithmscomplete bipartite subgraphs

Mathematics Subject Classification ID

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

Related Items (5)

Scale reduction techniques for computing maximum induced bicliques ⋮ Unnamed Item ⋮ Bicolored independent sets and bicliques ⋮ An exact exponential time algorithm for counting bipartite cliques ⋮ A convexity upper bound for the number of maximal bicliques of a bipartite graph

Cites Work

• Generating bicliques of a graph in lexicographic order
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• The maximum edge biclique problem is NP-complete
• An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover
• On Bipartite and Multipartite Clique Problems
• Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations
• Approximating Clique and Biclique Problems
• On Independent Sets and Bicliques in Graphs
• Node-and edge-deletion NP-complete problems
• Unnamed Item

This page was built for publication: Exact exponential-time algorithms for finding bicliques