An exact exponential time algorithm for counting bipartite cliques

DOI10.1016/j.ipl.2012.04.001zbMath1243.05227MaRDI QIDQ436594

Konstantin Kutzkov

Publication date: 25 July 2012

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

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

zbMATH Keywords

analysis of algorithms; counting bipartite cliques; exact exponential time algorithms

Mathematics Subject Classification ID

05C30: Enumeration in graph theory

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

New exact algorithms for the 2-constraint satisfaction problem

Cites Work

• Unnamed Item
• Bicolored independent sets and bicliques
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• Exact exponential-time algorithms for finding bicliques
• Fast algorithms for max independent set
• On independent sets and bicliques in graphs
• An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• A measure & conquer approach for the analysis of exact algorithms
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Set Partitioning via Inclusion-Exclusion
• Approximating Clique and Biclique Problems
• A full derandomization of schöning's k-SAT algorithm