The Parameterized Complexity of k-B<scp>iclique</scp>

DOI10.1137/1.9781611973730.41zbMath1371.68118arXiv1406.3700OpenAlexW2565184432MaRDI QIDQ5363087

Bingkai Lin

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.3700

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (15)

Tractability in constraint satisfaction problems: a survey ⋮ Assessing the Computational Complexity of Multi-layer Subgraph Detection ⋮ Scale reduction techniques for computing maximum induced bicliques ⋮ On the kernelization of split graph problems ⋮ The parameterized space complexity of embedding along a path ⋮ Hardness and algorithms for electoral manipulation under media influence ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Parameterized Dynamic Variants of Red-Blue Dominating Set ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ FPT algorithms for domination in sparse graphs and beyond ⋮ Unnamed Item ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices

This page was built for publication: The Parameterized Complexity of k-B<scp>iclique</scp>