Skip to Main content Skip to Navigation
Conference papers

Caractérisation de la complexité des classes de CSP définies par des motifs interdits à 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-00811871
Contributor : Guillaume Escamocher <>
Submitted on : Thursday, April 11, 2013 - 11:23:06 AM
Last modification on : Friday, June 12, 2020 - 10:40:05 AM
Document(s) archivé(s) le : Friday, July 12, 2013 - 4:05:40 AM

File

Article8.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00811871, version 1

Citation

Martin Cooper, Guillaume Escamocher. Caractérisation de la complexité des classes de CSP définies par des motifs interdits à deux contraintes.. JFPC - Journées Francophones de Programmation par Contraintes - 2012, May 2012, Toulouse, France. ⟨hal-00811871⟩

Share

Metrics

Record views

197

Files downloads

1096