Theoretical analysis of singleton arc consistency and its extensions

DOI10.1016/j.artint.2007.09.001zbMath1182.68217OpenAlexW2095366129MaRDI QIDQ2389615

Romuald Debruyne, Christian Bessiere

Publication date: 17 July 2009

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2007.09.001

zbMATH Keywords

constraint satisfaction problemsdisjunctive constraintslocal consistencysingleton arc consistencybidirectional singleton arc consistencyconstructive disjunction

Mathematics Subject Classification ID

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

Related Items (14)

On neighbourhood singleton-style consistencies for qualitative spatial and temporal reasoning ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ Super-reparametrizations of weighted CSPs: properties and optimization perspective ⋮ On tree-preserving constraints ⋮ Efficient algorithms for singleton arc consistency ⋮ New algorithms for bidirectional singleton arc consistency ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ AllDifferent-based filtering for subgraph isomorphism ⋮ Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems ⋮ Peek arc consistency ⋮ Neighborhood singleton consistencies ⋮ Collective singleton-based consistency for qualitative constraint networks: theory and practice ⋮ Solving CSPs Using Weak Local Consistency

Uses Software

• cc(FD)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal k-consistency algorithm
• On the solution of traveling salesman problems
• Relational consistency algorithms and their application in finding subgraph and graph isomorphisms
• Consistency in networks of relations
• Using constraint metaknowledge to reduce arc consistency computation
• Networks of constraints: Fundamental properties and applications to picture processing
• An optimal coarse-grained arc consistency algorithm
• A Sufficient Condition for Backtrack-Free Search
• Synthesizing constraint expressions
• Design, implementation, and evaluation of the constraint language cc(FD)

This page was built for publication: Theoretical analysis of singleton arc consistency and its extensions