Theoretical analysis of singleton arc consistency and its extensions

DOI10.1016/J.ARTINT.2007.09.001MaRDI QIDQ2389615zbMATH OpenOpenAlexFDO

Authors R. 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)

Recommendations

• New algorithms for bidirectional singleton arc consistency
• Efficient algorithms for singleton arc consistency
• SAC and neighbourhood SAC
• Neighbourhood SAC: extensions and new algorithms
• Partial (neighbourhood) singleton arc consistency for constraint satisfaction problems

Cites work

• scientific article; zbMATH DE number 2080318 (Why is no real title available?)
• scientific article; zbMATH DE number 2084731 (Why is no real title available?)
• A Sufficient Condition for Backtrack-Free Search
• An optimal coarse-grained arc consistency algorithm
• An optimal k-consistency algorithm
• Consistency in networks of relations
• Design, implementation, and evaluation of the constraint language cc(FD)
• Domain filtering consistencies
• Networks of constraints: Fundamental properties and applications to picture processing
• On the solution of traveling salesman problems
• Relational consistency algorithms and their application in finding subgraph and graph isomorphisms
• Synthesizing constraint expressions
• Using constraint metaknowledge to reduce arc consistency computation

Cited in

(19)

• Collective singleton-based consistency for qualitative constraint networks: theory and practice
• Neighborhood singleton consistencies
• Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems
• Peek arc consistency
• Neighbourhood SAC: extensions and new algorithms
• On tree-preserving constraints
• On neighbourhood singleton-style consistencies for qualitative spatial and temporal reasoning
• Weak consistency notions for all the CSPs of bounded width
• SAC and neighbourhood SAC
• scientific article; zbMATH DE number 2080318 (Why is no real title available?)
• Partial (neighbourhood) singleton arc consistency for constraint satisfaction problems
• Efficient algorithms for singleton arc consistency
• Solving CSPs using weak local consistency
• CLAP: A New Algorithm for Promise CSPs
• On singleton arc consistency for CSPs defined by monotone patterns
• On singleton arc consistency for CSPs defined by monotone patterns
• AllDifferent-based filtering for subgraph isomorphism
• New algorithms for bidirectional singleton arc consistency
• Super-reparametrizations of weighted CSPs: properties and optimization perspective

Describes a project that uses

Uses Software

• cc(FD)

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

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