CSP for binary conservative relational structures

DOI10.1007/s00012-015-0358-8zbMath1356.08001arXiv1112.1099OpenAlexW3105727132MaRDI QIDQ2634708

Alexandr Kazda

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

zbMATH Keywords

cloneconstraint satisfaction problemweak near unanimitymeet-semidistributivity

Mathematics Subject Classification ID

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