2014
AUTHORSMartin C. Cooper , Achref El Mouelhi , Cyril Terrioux , Bruno Zanuttini
ABSTRACTA binary CSP instance satisfying the broken-triangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in arbitrary instances of binary CSP, thus providing a novel polynomial-time reduction operation. Extensive experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances with constraints of arbitrary arity and we investigate the theoretical relationship with resolution in SAT. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP. More... »
PAGES9-24
Principles and Practice of Constraint Programming
ISBN
978-3-319-10427-0
978-3-319-10428-7
http://scigraph.springernature.com/pub.10.1007/978-3-319-10428-7_5
DOIhttp://dx.doi.org/10.1007/978-3-319-10428-7_5
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1042377580
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Paul Sabatier University",
"id": "https://www.grid.ac/institutes/grid.15781.3a",
"name": [
"IRIT, University of Toulouse III, 31062\u00a0Toulouse, France"
],
"type": "Organization"
},
"familyName": "Cooper",
"givenName": "Martin C.",
"id": "sg:person.011044367204.67",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011044367204.67"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Laboratoire des Sciences de l'Information et des Syst\u00e8mes",
"id": "https://www.grid.ac/institutes/grid.462878.7",
"name": [
"LSIS, Aix-Marseille University, 13397\u00a0Marseille, France"
],
"type": "Organization"
},
"familyName": "Mouelhi",
"givenName": "Achref El",
"id": "sg:person.013774213003.86",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013774213003.86"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Laboratoire des Sciences de l'Information et des Syst\u00e8mes",
"id": "https://www.grid.ac/institutes/grid.462878.7",
"name": [
"LSIS, Aix-Marseille University, 13397\u00a0Marseille, France"
],
"type": "Organization"
},
"familyName": "Terrioux",
"givenName": "Cyril",
"id": "sg:person.014232365062.45",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014232365062.45"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen",
"id": "https://www.grid.ac/institutes/grid.463910.9",
"name": [
"GREYC, University of Caen Basse-Normandie, 14032\u00a0Caen, France"
],
"type": "Organization"
},
"familyName": "Zanuttini",
"givenName": "Bruno",
"id": "sg:person.01171217521.45",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01171217521.45"
],
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1145/2505420.2505422",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008033687"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0004-3702(96)00018-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017098485"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.artint.2010.03.002",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1020699779"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11499107_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037721806",
"https://doi.org/10.1007/11499107_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11499107_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037721806",
"https://doi.org/10.1007/11499107_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-85958-1_35",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041159679",
"https://doi.org/10.1007/978-3-540-85958-1_35"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-85958-1_35",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041159679",
"https://doi.org/10.1007/978-3-540-85958-1_35"
],
"type": "CreativeWork"
}
],
"datePublished": "2014",
"datePublishedReg": "2014-01-01",
"description": "A binary CSP instance satisfying the broken-triangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in arbitrary instances of binary CSP, thus providing a novel polynomial-time reduction operation. Extensive experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances with constraints of arbitrary arity and we investigate the theoretical relationship with resolution in SAT. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP.",
"editor": [
{
"familyName": "O\u2019Sullivan",
"givenName": "Barry",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-10428-7_5",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isFundedItemOf": [
{
"id": "sg:grant.4521522",
"type": "MonetaryGrant"
}
],
"isPartOf": {
"isbn": [
"978-3-319-10427-0",
"978-3-319-10428-7"
],
"name": "Principles and Practice of Constraint Programming",
"type": "Book"
},
"name": "On Broken Triangles",
"pagination": "9-24",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-10428-7_5"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"c9dcfd66b80b9983d00cf9e5ff6a822dacbdec2e39fea12789bf6ac34120b125"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1042377580"
]
}
],
"publisher": {
"location": "Cham",
"name": "Springer International Publishing",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-10428-7_5",
"https://app.dimensions.ai/details/publication/pub.1042377580"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T12:34",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8663_00000269.jsonl",
"type": "Chapter",
"url": "http://link.springer.com/10.1007/978-3-319-10428-7_5"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-10428-7_5'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-10428-7_5'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-10428-7_5'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-10428-7_5'
This table displays all metadata directly associated to this object as RDF triples.
111 TRIPLES
23 PREDICATES
32 URIs
20 LITERALS
8 BLANK NODES