Constraint Satisfaction Parameterized by Solution Size
From MaRDI portal
Publication:3012823
DOI10.1007/978-3-642-22006-7_36zbMath1333.68136MaRDI QIDQ3012823
Dániel Marx, Andrei A. Bulatov
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_36
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- Parameterized complexity of constraint satisfaction problems
- How to determine the expressive power of constraints
- The Approximability of Constraint Satisfaction Problems
- On the Hardness of Losing Weight
- Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
- Preprocessing of Min Ones Problems: A Dichotomy
- The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
- Closure properties of constraints
- Monotone monadic SNP and constraint satisfaction
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Principles and Practice of Constraint Programming – CP 2004