Exact exponential-time algorithms for finding bicliques

DOI10.1016/J.IPL.2010.10.020MaRDI QIDQ1944039zbMATH OpenOpenAlexFDO

Authors Daniel Binkele-Raible, Henning Fernau, 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

bicliquescomplete bipartite subgraphsexact exponential-time algorithmsgraph algorithmsNP-hard problem

Mathematics Subject Classification ID

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

Recommendations

• An exact exponential time algorithm for counting bipartite cliques
• Theoretical Computer Science
• Approximating Clique and Biclique Problems
• The exponential time hypothesis and the parameterized clique problem
• Algorithms for finding biclique covers of graphs with bounded pathwidth
• Linear time algorithm for computing a small biclique in graphs without long induced paths
• Algorithms for \#BIS-hard problems on expander graphs
• Algorithms for #BIS-hard problems on expander graphs
• Efficient enumeration of maximal induced bicliques
• Graph-Theoretic Concepts in Computer Science

Cites work

• An efficient exact algorithm for constraint bipartite vertex cover
• Approximating Clique and Biclique Problems
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations
• Generating bicliques of a graph in lexicographic order
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Node-and edge-deletion NP-complete problems
• On bipartite and multipartite clique problems
• On Independent Sets and Bicliques in Graphs
• The maximum edge biclique problem is NP-complete

Cited in

(13)

• Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs
• Algorithms for induced biclique optimization problems
• On independent sets and bicliques in graphs
• A convexity upper bound for the number of maximal bicliques of a bipartite graph
• Scale reduction techniques for computing maximum induced bicliques
• Linear time algorithm for computing a small biclique in graphs without long induced paths
• Algorithms for finding biclique covers of graphs with bounded pathwidth
• On Fast Enumeration of Pseudo Bicliques
• Bicolored independent sets and bicliques
• An exact exponential time algorithm for counting bipartite cliques
• Problems and invariants connected with bicliques and multicliques of graphs
• Algorithms for #BIS-hard problems on expander graphs
• Exact algorithms for biclique coloring

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

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