Caractérisation de la complexité des classes de CSP définies par des motifs interdits à deux contraintes

Martin C. Cooper; Guillaume Escamocher

Caractérisation de la complexité des classes de CSP définies par des motifs interdits à deux contraintes

Translated title of the contribution: Characterization of CSP complexity classes defined by forbidden patterns in two constraints

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. This has allowed us to discover new tractable classes.

Translated title of the contribution	Characterization of CSP complexity classes defined by forbidden patterns in two constraints
Original language	French
Pages	74-81
Number of pages	8
Publication status	Published - 2012
Externally published	Yes
Event	8th Journees Francophones de Programmation par Contraintes, JFPC 2012 - 8th French-speaking Conference on Constraint Programming, JFPC 2012 - Toulouse, France Duration: 22 May 2012 → 24 May 2012

Conference

Conference	8th Journees Francophones de Programmation par Contraintes, JFPC 2012 - 8th French-speaking Conference on Constraint Programming, JFPC 2012
Country/Territory	France
City	Toulouse
Period	22/05/12 → 24/05/12

Cite this

@conference{fe64888bcf4e488286487917aaf581e3,

title = "Caract{\'e}risation de la complexit{\'e} des classes de CSP d{\'e}finies par des motifs interdits {\`a} deux contraintes",

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. This has allowed us to discover new tractable classes.",

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

year = "2012",

language = "French",

pages = "74--81",

note = "8th Journees Francophones de Programmation par Contraintes, JFPC 2012 - 8th French-speaking Conference on Constraint Programming, JFPC 2012 ; Conference date: 22-05-2012 Through 24-05-2012",

}

Caractérisation de la complexité des classes de CSP définies par des motifs interdits à deux contraintes. / Cooper, Martin C.; Escamocher, Guillaume.
2012. 74-81 Paper presented at 8th Journees Francophones de Programmation par Contraintes, JFPC 2012 - 8th French-speaking Conference on Constraint Programming, JFPC 2012, Toulouse, France.

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

TY - CONF

T1 - Caractérisation de la complexité des classes de CSP définies par des motifs interdits à deux contraintes

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. This has allowed us to discover new tractable classes.

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. This has allowed us to discover new tractable classes.

UR - https://www.scopus.com/pages/publications/84875383967

M3 - Paper

AN - SCOPUS:84875383967

SP - 74

EP - 81

T2 - 8th Journees Francophones de Programmation par Contraintes, JFPC 2012 - 8th French-speaking Conference on Constraint Programming, JFPC 2012

Y2 - 22 May 2012 through 24 May 2012

ER -

Caractérisation de la complexité des classes de CSP définies par des motifs interdits à deux contraintes

Abstract

Conference

Other files and links

Cite this