Broken triangles revisited

Simple item page
dc.contributor.authorCooper, Martin C.
dc.contributor.authorDuchein, Aymeric
dc.contributor.authorEscamocher, Guillaume
dc.contributor.editorPesant, Gilles
dc.contributor.funderEngineering and Physical Sciences Research Councilen
dc.contributor.funderAgence Nationale de la Rechercheen
dc.date.accessioned2022-07-27T15:39:13Z
dc.date.available2022-07-27T15:39:13Z
dc.date.issued2015-08-13
dc.date.updated2022-07-27T15:25:02Z
dc.description.abstractA 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.en
dc.description.sponsorshipL'Agence Nationale de la Recherche (ANR Project ANR-10-BLAN-0210); Engineering and Physical Sciences Research Council, UK ( EPSRC grant EP/L021226/1)en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationCooper, 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_5en
dc.identifier.doi10.1007/978-3-319-23219-5 5en
dc.identifier.endpage73en
dc.identifier.isbn978-3-319-23219-5
dc.identifier.isbn978-3-319-23218-8
dc.identifier.issn0302-9743
dc.identifier.journaltitleLecture Notes in Computer Scienceen
dc.identifier.startpage58en
dc.identifier.urihttps://hdl.handle.net/10468/13415
dc.identifier.volume9255en
dc.language.isoenen
dc.publisherSpringeren
dc.relation.projectinfo:eu-repo/grantAgreement/UKRI/EPSRC/EP/L021226/1/GB/Constraint Network Tractability: Beyond Structure and Language/en
dc.relation.projectinfo:eu-repo/grantAgreement/ANR//ANR-10-BLAN-0210/FR/Tractability for Understanding and Pushing forward the Limits of Efficient Solvers/TUPLESen
dc.relation.urihttps://doi.org/10.1007/978-3-319-23219-5_5
dc.rights© 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_5en
dc.subjectConstraint Satisfactionen
dc.subjectConstraint Satisfaction Problemen
dc.subjectDomain Reductionen
dc.subjectNeighbourhood Substitutionen
dc.subjectSixth Pointen
dc.titleBroken triangles revisiteden
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
cooper_2015_AV.pdf
Size:
159.23 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items