An optimal coarse-grained arc consistency algorithm
From MaRDI portal
Publication:2457664
DOI10.1016/j.artint.2005.02.004zbMath1132.68691OpenAlexW2099980081MaRDI QIDQ2457664
Yuan Lin Zhang, Roland H. C. Yap, Jean-Charles Régin, Christian Bessiere
Publication date: 23 October 2007
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-00105310/file/D550.PDF
constraint networksnon-binary constraintsarc consistencypath consistencyconstraint programming systems
Related Items (28)
Strong local consistency algorithms for table constraints ⋮ Reformulation of global constraints based on constraints checkers ⋮ Theoretical analysis of singleton arc consistency and its extensions ⋮ Solving quantified constraint satisfaction problems ⋮ Domain filtering consistencies for non-binary constraints ⋮ Properties of tree convex constraints ⋮ On the speed of constraint propagation and the time complexity of arc consistency testing ⋮ On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ On tree-preserving constraints ⋮ Efficient algorithms for singleton arc consistency ⋮ New algorithms for max restricted path consistency ⋮ STR2: optimized simple tabular reduction for table constraints ⋮ Path Consistency by Dual Consistency ⋮ New algorithms for bidirectional singleton arc consistency ⋮ Generating custom propagators for arbitrary constraints ⋮ Domain consistency with forbidden values ⋮ Automatic generation of redundant models for permutation constraint satisfaction problems ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems ⋮ An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints ⋮ A polynomial relational class of binary CSP ⋮ Parameterized Complexity of the Workflow Satisfiability Problem ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ Reasoning from last conflict(s) in constraint programming ⋮ Efficient Algorithms for Functional Constraints ⋮ Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns ⋮ STR3: a path-optimal filtering algorithm for table constraints ⋮ Variable and value elimination in binary constraint satisfaction via forbidden patterns
Uses Software
Cites Work
- Arc consistency for factorable relations.
- Network-based heuristics for constraint-satisfaction problems
- Relational consistency algorithms and their application in finding subgraph and graph isomorphisms
- A generic arc-consistency algorithm and its specializations
- Consistency in networks of relations
- Using constraint metaknowledge to reduce arc consistency computation
- Radio link frequency assignment
- An empirical study of phase transitions in binary constraint satisfaction problems
- Unnamed Item
This page was built for publication: An optimal coarse-grained arc consistency algorithm
