Revisiting Neighborhood Inverse Consistency on Binary CSPs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2012

Revisiting Neighborhood Inverse Consistency on Binary CSPs

Résumé

Our goal is to investigate the definition and application of strong consistency properties on the dual graphs of binary Constraint Satisfaction Problems (CSPs). As a first step in that direction, we study the structure of the dual graph of binary CSPs, and show how it can be arranged in a triangle-shaped grid. We then study, in this context, Relational Neighborhood Inverse Consistency (RNIC), which is a con- sistency property that we had introduced for non-binary CSPs. We discuss how the structure of the dual graph of binary CSPs affects the consistency level enforced by RNIC. Then, we compare, both theoreti- cally and empirically, RNIC to Neighborhood Inverse Consistency (NIC) and strong Conservative Dual Consistency (sCDC), which are higher- level consistency properties useful for solving difficult problem instances. We show that all three properties are pairwise incomparable.
Fichier principal
Vignette du fichier
cp12-rnic.pdf (919.34 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00748179 , version 1 (05-11-2012)

Identifiants

Citer

Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere. Revisiting Neighborhood Inverse Consistency on Binary CSPs. CP 2012 - 18th International Conference on Principles and Practice of Constraint Programming, Oct 2012, Québec City, Canada. pp.688-703, ⟨10.1007/978-3-642-33558-7_50⟩. ⟨lirmm-00748179⟩
145 Consultations
415 Téléchargements

Altmetric

Partager

More