On the Parameterized Complexity of Biclique Cover and Partition

DOI10.4230/LIPIcs.IPEC.2016.11zbMath1398.68221OpenAlexW2591896645MaRDI QIDQ4634394

Davis Issac, Andreas Karrenbauer, L. Sunil Chandran

Publication date: 10 April 2018

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/6929/pdf/LIPIcs-IPEC-2016-11.pdf/

zbMATH Keywords

lower boundbiclique cover/partitionlinear algebra in finite fields

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Unnamed Item ⋮ Parameterized low-rank binary matrix approximation ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Graph square roots of small distance from degree one graphs ⋮ On some FPT problems without polynomial Turing compressions