Variable Elimination in Binary CSP via Forbidden Patterns
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 517-522.
Abstract
A variable elimination rule allows the polynomial-time 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.
@inproceedings{ijcai2013p84,
title = {Variable Elimination in Binary CSP via Forbidden Patterns},
author = {Cohen, David A. and Cooper, Martin C. and Escamocher, Guillaume and Zivný, Stanislav},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {517--522},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/84},
}
TY - CPAPER TI - Variable Elimination in Binary CSP via Forbidden Patterns AU - Cohen, David A. AU - Cooper, Martin C. AU - Escamocher, Guillaume AU - Zivný, Stanislav T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 517 EP - 522 UR - https://ijcai.org/proceedings/2013/84 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
