On singleton arc consistency for CSPs defined by monotone patterns
From MaRDI portal
Publication:1739115
DOI10.1007/s00453-018-0498-2zbMath1421.68151WikidataQ90101886 ScholiaQ90101886MaRDI QIDQ1739115
Stanislav Živný, David A. Cohen, Martin C. Cooper, Clément Carbonnel
Publication date: 25 April 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0498-2
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
- 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
- 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