A new tractable class of constraint satisfaction problems
From MaRDI portal
Publication:1776199
DOI10.1007/s10472-005-1810-9zbMath1075.68082OpenAlexW2155002729MaRDI QIDQ1776199
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
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
