Skip to Main content Skip to Navigation
Conference papers

Making Bound Consistency as Effective as Arc Consistency

Christian Bessière 1 Thierry Petit 2, 3 Bruno Zanuttini 4
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
4 Equipe MAD - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image et Instrumentation de Caen
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Christian Bessiere Connect in order to contact the contributor
Submitted on : Friday, February 14, 2014 - 3:18:53 PM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM
Long-term archiving on: : Thursday, May 15, 2014 - 9:40:57 AM


Files produced by the author(s)


  • HAL Id : lirmm-00382609, version 1


Christian Bessière, 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⟩



Record views


Files downloads