A new tractable class of constraint satisfaction problems

DOI10.1007/s10472-005-1810-9zbMath1075.68082OpenAlexW2155002729MaRDI QIDQ1776199

Victor Dalmau

Publication date: 20 May 2005

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-005-1810-9

zbMATH Keywords

complexityconstraint satisfaction problempara-primal algebrapara-primal problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Classical propositional logic (03B05)

Related Items

Tractability in constraint satisfaction problems: a survey, The complexity of constraint satisfaction games and QCSP, Towards a dichotomy theorem for the counting constraint satisfaction problem, Colouring, constraint satisfaction, and complexity, Quantified Constraints in Twenty Seventeen, Parameterized Complexity of the Workflow Satisfiability Problem, Recent Results on the Algebraic Approach to the CSP, Introduction to the Maximum Solution Problem, Testing for edge terms is decidable, Periodic constraint satisfaction problems: Tractable subclasses

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• Network-based heuristics for constraint-satisfaction problems
• Plain para primal algebras
• A generic arc-consistency algorithm and its specializations
• Consistency in networks of relations
• Para primal algebras
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Fast parallel constraint satisfaction
• Decomposing constraint satisfaction problems using database techniques
• Characterising tractable constraints
• Learnability of quantified formulas.
• Networks of constraints: Fundamental properties and applications to picture processing
• Constraint relaxation may be perfect
• Combinatorial problems raised from 2-semilattices
• A sufficient condition for backtrack-bounded search
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• On the minimality and global consistency of row-convex constraint networks
• Closure properties of constraints
• The complexity of satisfiability problems
• Homogeneous operations and homogeneous algebras
• The complexity of theorem-proving procedures
• Tractable constraints on ordered domains