CSP for binary conservative relational structures
From MaRDI portal
Publication:2634708
DOI10.1007/s00012-015-0358-8zbMath1356.08001arXiv1112.1099OpenAlexW3105727132MaRDI QIDQ2634708
Publication date: 18 February 2016
Published in: Algebra Universalis (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1112.1099
Combinatorics in computer science (68R05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Subalgebras, congruence relations (08A30) Equational classes, universal algebra in model theory (03C05) Relational systems, laws of composition (08A02)
Related Items
Tractability in constraint satisfaction problems: a survey, The smallest hard trees, Algebra and the Complexity of Digraph CSPs: a Survey
Cites Work
- Unnamed Item
- Unnamed Item
- Universal algebra and hardness results for constraint satisfaction problems
- Characterizations of several Maltsev conditions.
- On digraph coloring problems and treewidth duality
- Closed systems of functions and predicates
- Complexity of conservative constraint satisfaction problems
- The structure of finite algebras
- The shape of congruence lattices
- Constraint Satisfaction Problems of Bounded Width
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- On the Reduction of the CSP Dichotomy Conjecture to Digraphs