Parameterized complexity and kernelizability of max ones and exact ones problems
type: Item
instance of: scholarly article
zbMATH Open document ID: 1347.68183
DOI: 10.1145/2858787
author: Stefan Kratsch
author: Dániel Marx
author: Magnus Wahlström
published in: ACM Transactions on Computation Theory
publication date: 2016-10-24T00:00:00Z
full work available at URL: http://eprints.sztaki.hu/9046/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6642912
zbMATH Keywords: CSP
zbMATH Keywords: FPT algorithms
zbMATH Keywords: complexity characterization
zbMATH Keywords: kernelization
MaRDI profile type: Publication
OpenAlex ID: W2253657605
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: On problems without polynomial kernels
cites work: Kernel bounds for disjoint cycles and disjoint paths
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Structure identification of Boolean relations and plain bases for co-clones
cites work: Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
cites work: On the Hamming distance of constraint satisfaction problems.
cites work: Incompressibility through Colors and IDs
cites work: Intersection Theorems for Systems of Sets
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: The approximability of constraint satisfaction problems
cites work: Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems
cites work: Preprocessing of Min Ones Problems: A Dichotomy
cites work: On the Structure of Polynomial Time Reducibility
cites work: Parameterized complexity of constraint satisfaction problems
cites work: Vertex packings: Structural properties and algorithms
cites work: The complexity of satisfiability problems
cites work: Finding paths of length \(k\) in \(O^{*}(2^k)\) time
title: Parameterized complexity and kernelizability of max ones and exact ones problems
description: scientific article; zbMATH DE number 6642912