On singleton arc consistency for CSPs defined by monotone patterns

DOI10.1007/S00453-018-0498-2MaRDI QIDQ1739115zbMATH OpenOpenAlexWikidataFDO

Authors Clément Carbonnel, David A. Cohen, M. C. Cooper, S. Zivny

Publication date 25 April 2019

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-018-0498-2

zbMATH Keywords

constraint satisfaction problemsforbidden patternssingleton arc consistency

Mathematics Subject Classification ID

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

Recommendations

• On singleton arc consistency for CSPs defined by monotone patterns
• Weak consistency notions for all the CSPs of bounded width
• The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
• scientific article; zbMATH DE number 6825406
• Arc consistency and friends

Cites work

• A Simple Algorithm for Mal'tsev Constraints
• A Sufficient Condition for Backtrack-Free Search
• An optimal coarse-grained arc consistency algorithm
• Applying constraint satisfaction techniques to job shop scheduling
• Arc consistency and friends
• Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• Characterising tractable constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Constraint satisfaction problems: Algorithms and applications
• Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
• Handbook of constraint programming.
• scientific article; zbMATH DE number 6825406 (Why is no real title available?)
• Hybrid tractability of valued constraint problems
• On singleton arc consistency for CSPs defined by monotone patterns
• On the Power of k-Consistency
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The power of propagation: when GAC is enough
• The tractability of CSP classes defined by forbidden patterns
• Theoretical analysis of singleton arc consistency and its extensions
• Tractability and learnability arising from algebras with few subpowers
• Variable and value elimination in binary constraint satisfaction via forbidden patterns
• Varieties with few subalgebras of powers
• Weak consistency notions for all the CSPs of bounded width

Cited in

(8)

• Galois connections for patterns: an algebra of labelled graphs
• Regular pattern-free coloring
• On singleton arc consistency for CSPs defined by monotone patterns
• scientific article; zbMATH DE number 2080326 (Why is no real title available?)
• scientific article; zbMATH DE number 6825406 (Why is no real title available?)
• Weak consistency notions for all the CSPs of bounded width
• The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
• Solving CSPs using weak local consistency

This page was built for publication: On singleton arc consistency for CSPs defined by monotone patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1739115)