OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Variable Elimination in Binary CSP via Forbidden Patterns

Cohen, David A. and Cooper, Martin C. and Escamocher, Guillaume and Zivny, Stanislav Variable Elimination in Binary CSP via Forbidden Patterns. (2013) In: International Joint Conference on Artificial Intelligence - IJCAI 2013, 3 August 2013 - 9 August 2013 (Beijing, China).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


A variable elimination rule allows the polynomialtime identification of certain variables whose elimination does not affect the satisfiability of an instance. Variable elimination in the constraint satisfaction problem (CSP) can be used in preprocessing or during search to reduce search space size. We show that there are essentially just four variable elimination rules defined by forbidding generic sub-instances, known as irreducible patterns, in arc-consistent CSP instances. One of these rules is the Broken Triangle Property, whereas the other three are novel.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to AAAI press editor. The definitive version is available at http://www.aaai.org/Press/Proceedings/ijcai13.php
HAL Id:hal-01141616
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > University of London (UNITED KINGDOM)
Other partners > University of Warwick (UNITED KINGDOM)
Laboratory name:
Agence nationale de la recherche (FRANCE)
Deposited On:13 Apr 2015 12:09

Repository Staff Only: item control page