Nearly Tight Approximability Results for Minimum Biclique Cover and Partition

DOI10.1007/978-3-662-44777-2_20zbMath1423.68590OpenAlexW1508674555MaRDI QIDQ2921408

Eugenia Holm, Sandy Heydrich, Andreas Karrenbauer, Parinya Chalermsook

Publication date: 8 October 2014

Published in: Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-44777-2_20

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (10)

Property testing of the Boolean and binary rank ⋮ On minimizing regular expressions without Kleene star ⋮ Upper bounds on the Boolean rank of Kronecker products ⋮ On the intractability landscape of digraph intersection representations ⋮ The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions ⋮ Modeling combinatorial disjunctive constraints via junction trees ⋮ Toward quality assessment of Boolean matrix factorizations ⋮ Unnamed Item ⋮ Efficient approximation for restricted biclique cover problems ⋮ The biclique covering number of grids

This page was built for publication: Nearly Tight Approximability Results for Minimum Biclique Cover and Partition