Cooper, Martin C. and Duchein, Aymeric and Escamocher, Guillaume Broken Triangles Revisited. (2015) In: 21st International Conference on Principles and Practice of Constraint Programming (CP 2015), 31 August 2015 - 4 September 2015 (Cork, Ireland).
|
(Document in English)
PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 387kB |
Official URL: http://dx.doi.org/10.1007/978-3-319-23219-5_5
Abstract
A broken triangle is a pattern of (in)compatibilities between assignments in a binary CSP (constraint satisfaction problem). In the absence of certain broken triangles, satisfiability-preserving domain reductions are possible via merging of domain values. We investigate the possibility of maximising the number of domain reduction operations by the choice of the order in which they are applied, as well as their interaction with arc consistency operations. It turns out that it is NP-hard to choose the best order.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Additional Information: | Thanks to Springer editor. This papers appears in Volume 9255 Lecture Notes in Computer Science ISSN : 0302-9743. ISBN: 978-3-319-23218-8. The original PDF is available at: http://link.springer.com/chapter/10.1007%2F978-3-319-23219-5_5 |
| HAL Id: | hal-01343049 |
| Audience (conference): | International conference proceedings |
| Uncontrolled Keywords: | |
| Institution: | French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE) Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE) Other partners > University College Cork (IRELAND) Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE) Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE) Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE) |
| Laboratory name: | |
| Statistics: | download |
| Deposited On: | 23 Jun 2016 11:51 |
Repository Staff Only: item control page
