Broken triangles revisited

Thumbnail Image
Files
cooper_2015_AV.pdf(159.23 KB)
Accepted version
Date
2015-08-13
Authors
Cooper, Martin C.
Duchein, Aymeric
Escamocher, Guillaume
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Published Version
10.1007/978-3-319-23219-5 5
Research Projects
Organizational Units
Journal Issue
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.
Description
Keywords
Constraint Satisfaction , Constraint Satisfaction Problem , Domain Reduction , Neighbourhood Substitution , Sixth Point
Citation
Cooper, M.C., Duchein, A. and Escamocher, G. (2015) ‘Broken Triangles Revisited’, CP 2015, Cork, Ireland 31 Aug-04 Sept., In: Pesant, G. (ed.) Principles and Practice of Constraint Programming, CP 2015, Lecture Notes in Computer Science, vol 9255, pp. 58-73 Springer, Cham. doi: 10.1007/978-3-319-23219-5_5
Link to publisher’s version
https://doi.org/10.1007/978-3-319-23219-5_5
URI
https://hdl.handle.net/10468/13415
Collections
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items
Copyright
© Springer International Publishing Switzerland 2015. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-319-23219-5_5