Skip to Main content Skip to Navigation
Conference papers

Revisiting Neighborhood Inverse Consistency on Binary CSPs

Robert J. Woodward 1 Shant Karakashian 1 Berthe Y. Choueiry 1 Christian Bessière 2
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00748179
Contributor : Joël Quinqueton <>
Submitted on : Monday, November 5, 2012 - 9:31:56 AM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM
Long-term archiving on: : Wednesday, February 6, 2013 - 3:53:50 AM

File

cp12-rnic.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00748179, version 1

Collections

Citation

Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessière. Revisiting Neighborhood Inverse Consistency on Binary CSPs. CP: Principles and Practice of Constraint Programming, Oct 2012, Québec City, Canada. pp.688-703. ⟨lirmm-00748179⟩

Share

Metrics

Record views

259

Files downloads

523