Ontology type: schema:Chapter Open Access: True
2016
AUTHORSMartin C. Cooper , Achref El Mouelhi , Cyril Terrioux
ABSTRACTBroken triangles constitute an important concept not only for solving constraint satisfaction problems in polynomial time, but also for variable elimination or domain reduction by merging domain values. Specifically, for a given variable in a binary arc-consistent CSP, if no broken triangle occurs on any pair of values, then this variable can be eliminated while preserving satisfiability. More recently, it has been shown that even when this rule cannot be applied, it could be possible that for a given pair of values no broken triangle occurs. In this case, we can apply a domain-reduction operation which consists in merging these values while preserving satisfiability. In this paper we show that under certain conditions, and even if there are some broken triangles on a pair of values, these values can be merged without changing the satisfiability of the instance. This allows us to define a stronger merging operation and a new tractable class of binary CSP instances. We report experimental trials on benchmark instances. More... »
PAGES173-188
Principles and Practice of Constraint Programming
ISBN
978-3-319-44952-4
978-3-319-44953-1
http://scigraph.springernature.com/pub.10.1007/978-3-319-44953-1_12
DOIhttp://dx.doi.org/10.1007/978-3-319-44953-1_12
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1020683575
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/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"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": {
"name": [
"IRIT, University of Toulouse III"
],
"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": {
"name": [
"Aix-Marseille Universit\u00e9, CNRS, ENSAM, Universit\u00e9 de Toulon, LSIS UMR 7296"
],
"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": {
"name": [
"Aix-Marseille Universit\u00e9, CNRS, ENSAM, Universit\u00e9 de Toulon, LSIS UMR 7296"
],
"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"
}
],
"citation": [
{
"id": "https://doi.org/10.1016/0004-3702(77)90007-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001107257"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10601-015-9198-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006425951",
"https://doi.org/10.1007/s10601-015-9198-6"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1080/0952813x.2012.721138",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007097894"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-23219-5_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008447517",
"https://doi.org/10.1007/978-3-319-23219-5_6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10601-015-9185-y",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017742435",
"https://doi.org/10.1007/s10601-015-9185-y"
],
"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": "https://doi.org/10.1145/2480362.2480382",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024497181"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-58601-6_86",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026133979",
"https://doi.org/10.1007/3-540-58601-6_86"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2933575.2933587",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026500634"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.jcss.2015.02.001",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030760395"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.artint.2016.02.001",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034742371"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0020-0255(74)90008-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042040952"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0020-0255(74)90008-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042040952"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-10428-7_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042377580",
"https://doi.org/10.1007/978-3-319-10428-7_5"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/ictai.2014.73",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094203319"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2903220.2903230",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1096186874"
],
"type": "CreativeWork"
}
],
"datePublished": "2016",
"datePublishedReg": "2016-01-01",
"description": "Broken triangles constitute an important concept not only for solving constraint satisfaction problems in polynomial time, but also for variable elimination or domain reduction by merging domain values. Specifically, for a given variable in a binary arc-consistent CSP, if no broken triangle occurs on any pair of values, then this variable can be eliminated while preserving satisfiability. More recently, it has been shown that even when this rule cannot be applied, it could be possible that for a given pair of values no broken triangle occurs. In this case, we can apply a domain-reduction operation which consists in merging these values while preserving satisfiability. In this paper we show that under certain conditions, and even if there are some broken triangles on a pair of values, these values can be merged without changing the satisfiability of the instance. This allows us to define a stronger merging operation and a new tractable class of binary CSP instances. We report experimental trials on benchmark instances.",
"editor": [
{
"familyName": "Rueher",
"givenName": "Michel",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-44953-1_12",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-319-44952-4",
"978-3-319-44953-1"
],
"name": "Principles and Practice of Constraint Programming",
"type": "Book"
},
"name": "Extending Broken Triangles and Enhanced Value-Merging",
"pagination": "173-188",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-44953-1_12"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"628d067d90238638b4d929ecb06940b368c51b30a55c766af7502cd08396b445"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1020683575"
]
}
],
"publisher": {
"location": "Cham",
"name": "Springer International Publishing",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-44953-1_12",
"https://app.dimensions.ai/details/publication/pub.1020683575"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T13:27",
"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_8664_00000256.jsonl",
"type": "Chapter",
"url": "http://link.springer.com/10.1007/978-3-319-44953-1_12"
}
]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-44953-1_12'
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-44953-1_12'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-44953-1_12'
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-44953-1_12'
This table displays all metadata directly associated to this object as RDF triples.
132 TRIPLES
23 PREDICATES
42 URIs
20 LITERALS
8 BLANK NODES