TY - GEN
T1 - A dichotomy for 2-constraint forbidden CSP patterns
AU - Cooper, Martin C.
AU - Escamocher, Guillaume
PY - 2012
Y1 - 2012
N2 - Novel tractable classes of the binary CSP (constraint satisfaction problem) have recently been discovered by studying classes of instances defined by excluding subproblems described by patterns. The complete characterisation of all tractable classes defined by forbidden patterns is a challenging problem. We demonstrate a dichotomy in the case of forbidden patterns consisting of two constraints.
AB - Novel tractable classes of the binary CSP (constraint satisfaction problem) have recently been discovered by studying classes of instances defined by excluding subproblems described by patterns. The complete characterisation of all tractable classes defined by forbidden patterns is a challenging problem. We demonstrate a dichotomy in the case of forbidden patterns consisting of two constraints.
UR - https://www.scopus.com/pages/publications/84868290027
M3 - Conference proceeding
AN - SCOPUS:84868290027
SN - 9781577355687
T3 - Proceedings of the National Conference on Artificial Intelligence
SP - 464
EP - 470
BT - AAAI-12 / IAAI-12 - Proceedings of the 26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference
T2 - 26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12
Y2 - 22 July 2012 through 26 July 2012
ER -