Theoretical Analysis of Singleton Arc Consistency - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2004

Theoretical Analysis of Singleton Arc Consistency

Romuald Debruyne


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.
Fichier principal
Vignette du fichier
ecai04ws-sac.pdf (147.3 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00108866 , version 1 (12-10-2019)


  • HAL Id : lirmm-00108866 , version 1


Christian Bessiere, 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⟩
202 View
34 Download


Gmail Facebook X LinkedIn More