The power of propagation: when GAC is enough

DOI10.1007/s10601-016-9251-0zbMath1387.90130MaRDI QIDQ1701225

David A. Cohen, Peter G. Jeavons

Publication date: 22 February 2018

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-016-9251-0

zbMATH Keywords

propagators; constraint satisfaction; global constraints; arc-consistency

Mathematics Subject Classification ID

90C10: Integer programming

Related Items

Binary constraint satisfaction problems defined by excluded topological minors, On singleton arc consistency for CSPs defined by monotone patterns, Unnamed Item

Uses Software

• CSPLib

Cites Work

• Unnamed Item
• Unnamed Item
• Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
• The complexity of completing partial Latin squares
• Global constraint catalogue: past, present and future
• A unified theory of structural tractability for constraint satisfaction problems
• Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
• Tree clustering for constraint networks
• Decomposing constraint satisfaction problems using database techniques
• A comparison of structural CSP decomposition methods
• Tractable decision for a constraint language implies tractable search
• Constraint satisfaction problems: convexity makes AllDifferent constraints tractable
• Constraint satisfaction with succinctly specified relations
• Tractable cases of the extended global cardinality constraint
• The complexity of reasoning with global constraints
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Optimization Methods for the Partner Units Problem
• On the Desirability of Acyclic Database Schemes
• The complexity of global cardinality constraints
• GAC Via Unit Propagation
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• A Sufficient Condition for Backtrack-Free Search
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
• Classifying the Complexity of Constraints Using Finite Algebras
• Principles and Practice of Constraint Programming – CP 2003
• Principles and Practice of Constraint Programming – CP 2003
• Principles and Practice of Constraint Programming – CP 2003
• Tractable constraints on ordered domains