On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
From MaRDI portal
Publication:3304113
DOI10.4230/LIPIcs.STACS.2018.19zbMath1487.68208arXiv1704.06215MaRDI QIDQ3304113
Stanislav Živný, Martin C. Cooper, Clément Carbonnel, David A. Cohen
Publication date: 5 August 2020
Full work available at URL: https://arxiv.org/abs/1704.06215
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Cites Work
- Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
- Hybrid tractability of valued constraint problems
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- Characterising tractable constraints
- Applying constraint satisfaction techniques to job shop scheduling
- The power of propagation: when GAC is enough
- Constraint satisfaction problems: Algorithms and applications
- Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
- Variable and value elimination in binary constraint satisfaction via forbidden patterns
- Theoretical analysis of singleton arc consistency and its extensions
- An optimal coarse-grained arc consistency algorithm
- The Tractability of CSP Classes Defined by Forbidden Patterns
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Varieties with few subalgebras of powers
- A Sufficient Condition for Backtrack-Free Search
- Weak consistency notions for all the CSPs of bounded width
- The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
- Arc consistency and friends
- Classifying the Complexity of Constraints Using Finite Algebras
- Tractability and Learnability Arising from Algebras with Few Subpowers
- On the Power of k-Consistency
- A Simple Algorithm for Mal'tsev Constraints