Skip to Main content Skip to Navigation
Conference papers

Theoretical Analysis of Singleton Arc Consistency

Christian Bessière 1 Romuald Debruyne 2
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Singleton arc consistency (SAC) is a local consistency that enhances the pruning capability of arc consistency by ensuring that the network can be made arc consistent after any assignment of a value to a variable. While some algorithms have been proposed in the literature to enforce SAC, a more in-depth theoretical analysis of this local consistency has never been published. In this paper, we give a lower bound to the time complexity of enforcing SAC, and we propose an algorithm that achieves this complexity, thus being optimal. We characterize some properties of SAC which are unusual for a local consistency. Based on some of these properties, we extend SAC to a more powerful local consistency that we compare to the existing local consistencies.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00108866
Contributor : Christine Carvalho de Matos <>
Submitted on : Saturday, October 12, 2019 - 6:57:32 PM
Last modification on : Thursday, June 25, 2020 - 3:04:41 AM
Document(s) archivé(s) le : Monday, January 13, 2020 - 2:21:45 PM

File

ecai04ws-sac.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00108866, version 1

Citation

Christian Bessière, Romuald Debruyne. Theoretical Analysis of Singleton Arc Consistency. Workshop on Modelling and Solving Problems with Constraints, Aug 2004, Valencia, Spain. pp.20-29. ⟨lirmm-00108866⟩

Share

Metrics

Record views

205

Files downloads

20