A Dichotomy for 2-Constraint Forbidden CSP Patterns

Martin C. Cooper; Guillaume Escamocher

A Dichotomy for 2-Constraint Forbidden CSP Patterns

Martin C. Cooper
, Guillaume Escamocher

Université Fédérale Toulouse Midi-Pyrénées

Research output: Contribution to conference › Paper › peer-review

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.

Original language	English
Pages	464-470
Number of pages	7
Publication status	Published - 2012
Externally published	Yes
Event	26th AAAI Conference on Artificial Intelligence, AAAI 2012 - Toronto, Canada Duration: 22 Jul 2012 → 26 Jul 2012

Conference

Conference	26th AAAI Conference on Artificial Intelligence, AAAI 2012
Country/Territory	Canada
City	Toronto
Period	22/07/12 → 26/07/12

Cite this

@conference{3ce8f8e248844f0a94a1ee77cd02850b,

title = "A Dichotomy for 2-Constraint Forbidden CSP Patterns",

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.",

author = "Cooper, \{Martin C.\} and Guillaume Escamocher",

note = "Publisher Copyright: Copyright {\textcopyright} 2012, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 26th AAAI Conference on Artificial Intelligence, AAAI 2012 ; Conference date: 22-07-2012 Through 26-07-2012",

year = "2012",

language = "English",

pages = "464--470",

}

TY - CONF

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/84906232623

M3 - Paper

AN - SCOPUS:84906232623

SP - 464

EP - 470

T2 - 26th AAAI Conference on Artificial Intelligence, AAAI 2012

Y2 - 22 July 2012 through 26 July 2012

ER -

A Dichotomy for 2-Constraint Forbidden CSP Patterns

Abstract

Conference

Other files and links

Cite this