Conference Papers Year : 2012

Revisiting Neighborhood Inverse Consistency on Binary CSPs

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.
Fichier principal
Vignette du fichier
cp12-rnic.pdf (919.34 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
147 View
427 Download

Altmetric

Share

More