On singleton arc consistency for CSPs defined by monotone patterns

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

zbMATH Keywords

constraint satisfaction problems; forbidden patterns; singleton arc consistency

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Galois connections for patterns: an algebra of labelled graphs, Regular pattern-free coloring

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