A combinatorial constraint satisfaction problem dichotomy classification conjecture
From MaRDI portal
Recommendations
- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
- A proof of the CSP dichotomy conjecture
- A new line of attack on the dichotomy conjecture
- On the reduction of the CSP dichotomy conjecture to digraphs
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
Cites work
- scientific article; zbMATH DE number 1670830 (Why is no real title available?)
- scientific article; zbMATH DE number 3650557 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1061261 (Why is no real title available?)
- scientific article; zbMATH DE number 1996252 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- A strong Mal'cev condition for locally finite varieties omitting the unary type
- An algebraic approach to multi-sorted constraints
- Classifying the Complexity of Constraints Using Finite Algebras
- Closed systems of functions and predicates
- Closure properties of constraints
- Colorings and homomorphisms of degenerate and bounded degree graphs
- Colouring, constraint satisfaction, and complexity
- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
- Complexity classifications of Boolean constraint satisfaction problems
- Constraints, MMSNP and expander relational structures
- Dichotomy for bounded degree \(H\)-colouring
- Existence theorems for weakly symmetric operations
- From graph coloring to constraint satisfaction: there and back again
- List homomorphisms of graphs with bounded degrees
- Networks of constraints: Fundamental properties and applications to picture processing
- On colorings of graphs without short cycles
- On highly ramsey infinite graphs
- On sparse graphs with given colorings and homomorphisms.
- On the algebraic structure of combinatorial problems
- On the complexity of H-coloring
- Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The Complexity of the Extendibility Problem for Finite Posets
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The NP-Completeness of Edge-Coloring
- The complexity of satisfiability problems
- \(H\)-coloring dichotomy revisited
Cited in
(12)- A polynomial algorithm for 3-compatible coloring and the stubborn list partition problem (the stubborn problem is stubborn no more)
- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
- In praise of homomorphisms
- On the reduction of the CSP dichotomy conjecture to digraphs
- A Probabilistic Approach to the Dichotomy Problem
- \(H\)-coloring degree-bounded (acyclic) digraphs
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- A new line of attack on the dichotomy conjecture
- A finer reduction of constraint problems to digraphs
- A new line of attack on the dichotomy conjecture
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- A strong Mal'cev condition for locally finite varieties omitting the unary type
This page was built for publication: A combinatorial constraint satisfaction problem dichotomy classification conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1041203)
