Complexity of conservative constraint satisfaction problems
From MaRDI portal
Recommendations
Cited in
(66)- Constraint satisfaction problems: convexity makes AllDifferent constraints tractable
- Consistent query answering for primary keys in Datalog
- Complexity of correspondence \(H\)-colourings
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- Dichotomy for tree-structured trigraph list homomorphism problems
- A quasi-Mal'cev condition with unexpected application.
- On planar valued CSPs
- Correspondence homomorphisms to reflexive graphs
- A dichotomy for minimum cost graph homomorphisms
- Minimum cost and list homomorphisms to semicomplete digraphs
- Dichotomy for finite tournaments of mixed-type
- CSP for binary conservative relational structures
- The complexity of constraint satisfaction revisited
- Tractability in constraint satisfaction problems: a survey
- Minimum cost homomorphisms with constrained costs
- Adjusted interval digraphs
- Minimax problems of discrete optimization invariant under majority operators
- Surjective \texttt{H}-colouring over reflexive digraphs
- Complexity of infinite-domain constraint satisfaction
- A Galois connection for valued constraint languages of infinite size
- Algebraic properties of valued constraint satisfaction problem
- Necessary conditions for tractability of valued CSPs
- scientific article; zbMATH DE number 4162262 (Why is no real title available?)
- The property of being polynomial for Mal’tsev constraint satisfaction problems
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- The complexity of surjective homomorphism problems-a survey
- The Complexity of Minimal Inference Problem for Conservative Constraint Languages
- Qualitative constraint satisfaction problems: an extended framework with landmarks
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Absorption in universal algebra and CSP
- The complexity of valued CSPs
- Algebra and the complexity of digraph CSPs: a survey
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- Consistent query answering for primary keys in logspace
- Testing the Complexity of a Valued CSP Language
- scientific article; zbMATH DE number 7561584 (Why is no real title available?)
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Time complexity of constraint satisfaction via universal algebra
- A proof of the CSP dichotomy conjecture
- Hybrid VCSPs with crisp and valued conservative templates
- On the computational complexity of non-dictatorial aggregation
- Constant-query testability of assignments to constraint satisfaction problems
- The power of linear programming for general-valued CSPs
- Gap theorems for robust satisfiability: Boolean CSPs and beyond
- Aggregation of votes with multiple positions on each issue
- The complexity of general-valued CSPs
- The power of Sherali-Adams relaxations for general-valued CSPs
- Binarisation for valued constraint satisfaction problems
- Bounded Tree-Width and CSP-Related Problems
- A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms
- Dynamic algorithms for classes of constraint satisfaction problems
- List homomorphisms to separable signed graphs
- CSP beyond tractable constraint languages
- Towards a dichotomy for the list switch homomorphism problem for signed graphs
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- The complexity of the distributed constraint satisfaction problem
- Graphs of finite algebras: maximality, rectangularity, and decomposition
- Graphs of finite algebras: edges, and connectivity
- Network satisfaction problems solved by k-consistency
- Solving promise equations over monoids and groups
- Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
- Solving promise equations over monoids and groups
- Aggregation of evaluations without unanimity
- Hard constraint satisfaction problems have hard gaps at location 1
- Digraph matrix partitions and trigraph homomorphisms
- Conservative constraint satisfaction re-revisited
This page was built for publication: Complexity of conservative constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946643)
