You are here

Broken Triangles Revisited

Authors: 

Martin Cooper, Aymeric Duchein, Guillaume Escamocher

Publication Type: 
Refereed Conference Meeting Proceeding
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.
Conference Name: 
CP 2015
Digital Object Identifer (DOI): 
10.1007/978-3-319-23219-5_5
Publication Date: 
13/08/2015
Pages: 
58-73
Conference Location: 
Ireland
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
Yes
Publication document: