Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
From MaRDI portal
Publication:2341755
DOI10.1016/j.dam.2014.10.035zbMath1311.05004MaRDI QIDQ2341755
Martin C. Cooper, Guillaume Escamocher
Publication date: 28 April 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.10.035
05A05: Permutations, words, matrices
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Hybrid Tractable Classes of Constraint Problems, Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems, Binary constraint satisfaction problems defined by excluded topological minors, On singleton arc consistency for CSPs defined by monotone patterns, Galois connections for patterns: an algebra of labelled graphs, Regular pattern-free coloring, Variable and value elimination in binary constraint satisfaction via forbidden patterns, On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hybrid tractability of valued constraint problems
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- Characterising tractable constraints
- Fundamental properties of neighbourhood substitution in constraint satisfaction problems
- An optimal coarse-grained arc consistency algorithm
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
- The Tractability of CSP Classes Defined by Forbidden Patterns
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of theorem-proving procedures
