Constraint satisfaction problems: complexity and algorithms

DOI10.1007/978-3-319-77313-1_1MaRDI QIDQ1647670zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov

Publication date 26 June 2018

Full work available at URL https://doi.org/10.1007/978-3-319-77313-1_1

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) History of computer science (68-03) Computational aspects of satisfiability (68R07)

Recommendations

• A proof of the CSP dichotomy conjecture
• scientific article; zbMATH DE number 1670830
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of constraint satisfaction: an algebraic approach
• Computational Complexity of Constraint Satisfaction

Cited in

(19)

• scientific article; zbMATH DE number 4162262 (Why is no real title available?)
• scientific article; zbMATH DE number 7651213 (Why is no real title available?)
• Algorithms and Constraint Programming
• Algebra and the complexity of digraph CSPs: a survey
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• Constraint satisfaction problems over semilattice block Mal'tsev algebras
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• Colouring, constraint satisfaction, and complexity
• Constraint Satisfaction Problems on Intervals and Lengths
• The complexity of constraint satisfaction: an algebraic approach
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• scientific article; zbMATH DE number 1390075 (Why is no real title available?)
• The complexity of constraint satisfaction revisited
• Constraint Satisfaction Parameterized by Solution Size
• Ideal membership problem over 3-element CSPs with dual discriminator polymorphism
• Computational Complexity of Constraint Satisfaction
• From graph coloring to constraint satisfaction: there and back again
• A proof of the CSP dichotomy conjecture
• scientific article; zbMATH DE number 1322793 (Why is no real title available?)

This page was built for publication: Constraint satisfaction problems: complexity and algorithms

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