TY - GEN
T1 - Broken triangles revisited
AU - Cooper, Martin C.
AU - Duchein, Aymeric
AU - Escamocher, Guillaume
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84944627825
U2 - 10.1007/978-3-319-23219-5_5
DO - 10.1007/978-3-319-23219-5_5
M3 - Conference proceeding
AN - SCOPUS:84944627825
SN - 9783319232188
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 58
EP - 73
BT - Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings
A2 - Pesant, Gilles
PB - Springer Verlag
T2 - 21st International Conference on the Principles and Practice of Constraint Programming, CP 2015
Y2 - 31 August 2015 through 4 September 2015
ER -