Complexity of conservative constraint satisfaction problems
DOI10.1145/1970398.1970400zbMATH Open1351.68113OpenAlexW2032487621WikidataQ130964103 ScholiaQ130964103MaRDI QIDQ2946643FDOQ2946643
Publication date: 17 September 2015
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1970398.1970400
Recommendations
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)
Cited In (55)
- The Power of Sherali--Adams Relaxations for General-Valued CSPs
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- Aggregation of Votes with Multiple Positions on Each Issue
- The complexity of surjective homomorphism problems-a survey
- Title not available (Why is that?)
- Tractability in constraint satisfaction problems: a survey
- The Complexity of Minimal Inference Problem for Conservative Constraint Languages
- The Complexity of General-Valued CSPs
- Binarisation for Valued Constraint Satisfaction Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dichotomy for finite tournaments of mixed-type
- CSP beyond tractable constraint languages
- Qualitative constraint satisfaction problems: an extended framework with landmarks
- Conservative constraint satisfaction re-revisited
- The Complexity of Valued CSPs
- List homomorphisms to separable signed graphs
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- Algebra and the Complexity of Digraph CSPs: a Survey
- Title not available (Why is that?)
- Title not available (Why is that?)
- Testing the Complexity of a Valued CSP Language
- Consistent query answering for primary keys in Datalog
- Minimax problems of discrete optimization invariant under majority operators
- Minimum Cost Homomorphisms with Constrained Costs
- Dichotomy for tree-structured trigraph list homomorphism problems
- Adjusted interval digraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On planar valued CSPs
- Bounded Tree-Width and CSP-Related Problems
- Algebraic Properties of Valued Constraint Satisfaction Problem
- CSP for binary conservative relational structures
- Digraph matrix partitions and trigraph homomorphisms
- Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
- Hard constraint satisfaction problems have hard gaps at location 1
- Time Complexity of Constraint Satisfaction via Universal Algebra
- Title not available (Why is that?)
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- The Power of Linear Programming for General-Valued CSPs
- Correspondence homomorphisms to reflexive graphs
- Complexity of correspondence \(H\)-colourings
- A quasi-Mal'cev condition with unexpected application.
- Necessary Conditions for Tractability of Valued CSPs
- Constant-Query Testability of Assignments to Constraint Satisfaction Problems
- A dichotomy for minimum cost graph homomorphisms
- Minimum cost and list homomorphisms to semicomplete digraphs
- On the Computational Complexity of Non-Dictatorial Aggregation
- A Galois Connection for Valued Constraint Languages of Infinite Size
- Dynamic algorithms for classes of constraint satisfaction problems
- Gap theorems for robust satisfiability: Boolean CSPs and beyond
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- Title not available (Why is that?)
- Graphs of finite algebras: maximality, rectangularity, and decomposition
- Graphs of finite algebras: edges, and connectivity
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)
