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

bidirectional singleton arc consistencyconstraint satisfaction problemsconstructive disjunctiondisjunctive constraintslocal consistencysingleton arc consistency

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

• 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
• scientific article; zbMATH DE number 2080318 (Why is no real title available?)
• scientific article; zbMATH DE number 2084731 (Why is no real title available?)
• 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

(21)

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

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)