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 metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Christine Carvalho de Matos Connect in order to contact the contributor
Submitted on : Saturday, October 12, 2019 - 6:57:32 PM
Last modification on : Monday, October 11, 2021 - 1:24:09 PM
Long-term archiving on: : Monday, January 13, 2020 - 2:21:45 PM


Files produced by the author(s)


  • HAL Id : lirmm-00108866, version 1


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⟩



Record views


Files downloads