Theoretical Analysis of Singleton Arc Consistency - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2004

Theoretical Analysis of Singleton Arc Consistency

Romuald Debruyne

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00108866 , version 1

Citer

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⟩
207 Consultations
34 Téléchargements

Partager

Gmail Facebook X LinkedIn More