A Dichotomy for 2-Constraint Forbidden CSP Patterns

AAAI 2012 pp. 464-470

doi:10.1609/AAAI.V26I1.8131 /aaai/2012/cooper2012aaai-dichotomy/

Abstract

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.

PDF AAAI Semantic Scholar

Cite

Text

Cooper and Escamocher. "A Dichotomy for 2-Constraint Forbidden CSP Patterns." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8131

Markdown

[Cooper and Escamocher. "A Dichotomy for 2-Constraint Forbidden CSP Patterns." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/cooper2012aaai-dichotomy/) doi:10.1609/AAAI.V26I1.8131

BibTeX

@inproceedings{cooper2012aaai-dichotomy,
  title     = {{A Dichotomy for 2-Constraint Forbidden CSP Patterns}},
  author    = {Cooper, Martin C. and Escamocher, Guillaume},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2012},
  pages     = {464-470},
  doi       = {10.1609/AAAI.V26I1.8131},
  url       = {https://mlanthology.org/aaai/2012/cooper2012aaai-dichotomy/}
}