Constraint Satisfaction Parameterized by Solution Size

DOI10.1007/978-3-642-22006-7_36MaRDI QIDQ3012823zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov, Dániel Marx

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Constraint satisfaction parameterized by solution size
• Parameterized complexity of constraint satisfaction problems
• Parameterized constraint satisfaction problems: a survey
• Constraint Satisfaction
• Constraint satisfaction -- algorithms and complexity analysis
• Solving quantified constraint satisfaction problems
• Constraint satisfaction problems: complexity and algorithms
• On approximate constraint satisfaction
• Computational Complexity of Constraint Satisfaction

Cites work

• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• How to determine the expressive power of constraints
• Monotone monadic SNP and constraint satisfaction
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• On the Hardness of Losing Weight
• Parameterized complexity of constraint satisfaction problems
• Preprocessing of min ones problems: a dichotomy
• Principles and Practice of Constraint Programming – CP 2004
• The approximability of constraint satisfaction problems
• The complexity of satisfiability problems
• The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT

Cited in

(2)

• Uniform CSP parameterized by solution size is in W[1]
• Constraint satisfaction parameterized by solution size

This page was built for publication: Constraint Satisfaction Parameterized by Solution Size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012823)