Making Bound Consistency as Effective as 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 : 2009

Making Bound Consistency as Effective as Arc Consistency

Résumé

We study under what conditions bound consistency (BC) and arc consistency (AC), two forms of propagation used in constraint solvers, are equivalent to each other. We show that they prune exactly the same values when the propagated constraint is connected row convex / closed under median and its complement is row convex. This characterization is exact for binary constraints. Since row convexity depends on the order of the values in the domains, we give polynomial algorithms for computing orders under which BC and AC are equivalent, if any.
Fichier principal
Vignette du fichier
bpz09.pdf (126.34 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00382609 , version 1 (14-02-2014)

Identifiants

  • HAL Id : lirmm-00382609 , version 1

Citer

Christian Bessiere, Thierry Petit, Bruno Zanuttini. Making Bound Consistency as Effective as Arc Consistency. IJCAI'09: 21st International Joint Conference on Artificial Intelligence, Jul 2009, Pasadena, CA, United States. pp.425-430. ⟨lirmm-00382609⟩
334 Consultations
163 Téléchargements

Partager

Gmail Facebook X LinkedIn More