On Broken Triangles View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2014

AUTHORS

Martin C. Cooper , Achref El Mouelhi , Cyril Terrioux , Bruno Zanuttini

ABSTRACT

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. More... »

PAGES

9-24

References to SciGraph publications

  • 2005. Effective Preprocessing in SAT Through Variable and Clause Elimination in THEORY AND APPLICATIONS OF SATISFIABILITY TESTING
  • 2008. Perfect Constraints Are Tractable in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-10428-7_5

    DOI

    http://dx.doi.org/10.1007/978-3-319-10428-7_5

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1042377580


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    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

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    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

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-10428-7_5 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nf0a9bc6917854b7499d945fb764835e9
    4 schema:citation sg:pub.10.1007/11499107_5
    5 sg:pub.10.1007/978-3-540-85958-1_35
    6 https://doi.org/10.1016/j.artint.2010.03.002
    7 https://doi.org/10.1016/s0004-3702(96)00018-5
    8 https://doi.org/10.1145/2505420.2505422
    9 schema:datePublished 2014
    10 schema:datePublishedReg 2014-01-01
    11 schema: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.
    12 schema:editor N95583989c32141d1962512e899993178
    13 schema:genre chapter
    14 schema:inLanguage en
    15 schema:isAccessibleForFree false
    16 schema:isPartOf N083b5e2bb9434f09af10f02dcb2d954d
    17 schema:name On Broken Triangles
    18 schema:pagination 9-24
    19 schema:productId N06eb6a7e93f14a5e8f3cadea36caf6fc
    20 N9f0dabff512b405b8972233702cb6a3a
    21 Ne311e1eaa3c04d788f43b2c3ac399de7
    22 schema:publisher Nb51ff24089b949bd94bd302c4650cb7a
    23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042377580
    24 https://doi.org/10.1007/978-3-319-10428-7_5
    25 schema:sdDatePublished 2019-04-15T12:34
    26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    27 schema:sdPublisher Na9ef997dfae14773a5a23cfffd432067
    28 schema:url http://link.springer.com/10.1007/978-3-319-10428-7_5
    29 sgo:license sg:explorer/license/
    30 sgo:sdDataset chapters
    31 rdf:type schema:Chapter
    32 N06eb6a7e93f14a5e8f3cadea36caf6fc schema:name doi
    33 schema:value 10.1007/978-3-319-10428-7_5
    34 rdf:type schema:PropertyValue
    35 N083b5e2bb9434f09af10f02dcb2d954d schema:isbn 978-3-319-10427-0
    36 978-3-319-10428-7
    37 schema:name Principles and Practice of Constraint Programming
    38 rdf:type schema:Book
    39 N600042ce384749bd882beef76019dd45 rdf:first sg:person.013774213003.86
    40 rdf:rest Nb9107a838697468da83a6e51d6da0524
    41 N95583989c32141d1962512e899993178 rdf:first N9d030e474260452e91881542ffd280e9
    42 rdf:rest rdf:nil
    43 N9d030e474260452e91881542ffd280e9 schema:familyName O’Sullivan
    44 schema:givenName Barry
    45 rdf:type schema:Person
    46 N9f0dabff512b405b8972233702cb6a3a schema:name readcube_id
    47 schema:value c9dcfd66b80b9983d00cf9e5ff6a822dacbdec2e39fea12789bf6ac34120b125
    48 rdf:type schema:PropertyValue
    49 Na9ef997dfae14773a5a23cfffd432067 schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 Nb51ff24089b949bd94bd302c4650cb7a schema:location Cham
    52 schema:name Springer International Publishing
    53 rdf:type schema:Organisation
    54 Nb9107a838697468da83a6e51d6da0524 rdf:first sg:person.014232365062.45
    55 rdf:rest Nc41998bff24642beb3ee1e86a06b2ce3
    56 Nc41998bff24642beb3ee1e86a06b2ce3 rdf:first sg:person.01171217521.45
    57 rdf:rest rdf:nil
    58 Ne311e1eaa3c04d788f43b2c3ac399de7 schema:name dimensions_id
    59 schema:value pub.1042377580
    60 rdf:type schema:PropertyValue
    61 Nf0a9bc6917854b7499d945fb764835e9 rdf:first sg:person.011044367204.67
    62 rdf:rest N600042ce384749bd882beef76019dd45
    63 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    64 schema:name Information and Computing Sciences
    65 rdf:type schema:DefinedTerm
    66 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Computation Theory and Mathematics
    68 rdf:type schema:DefinedTerm
    69 sg:grant.4521522 http://pending.schema.org/fundedItem sg:pub.10.1007/978-3-319-10428-7_5
    70 rdf:type schema:MonetaryGrant
    71 sg:person.011044367204.67 schema:affiliation https://www.grid.ac/institutes/grid.15781.3a
    72 schema:familyName Cooper
    73 schema:givenName Martin C.
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011044367204.67
    75 rdf:type schema:Person
    76 sg:person.01171217521.45 schema:affiliation https://www.grid.ac/institutes/grid.463910.9
    77 schema:familyName Zanuttini
    78 schema:givenName Bruno
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01171217521.45
    80 rdf:type schema:Person
    81 sg:person.013774213003.86 schema:affiliation https://www.grid.ac/institutes/grid.462878.7
    82 schema:familyName Mouelhi
    83 schema:givenName Achref El
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013774213003.86
    85 rdf:type schema:Person
    86 sg:person.014232365062.45 schema:affiliation https://www.grid.ac/institutes/grid.462878.7
    87 schema:familyName Terrioux
    88 schema:givenName Cyril
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014232365062.45
    90 rdf:type schema:Person
    91 sg:pub.10.1007/11499107_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037721806
    92 https://doi.org/10.1007/11499107_5
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/978-3-540-85958-1_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041159679
    95 https://doi.org/10.1007/978-3-540-85958-1_35
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/j.artint.2010.03.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020699779
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/s0004-3702(96)00018-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017098485
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1145/2505420.2505422 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008033687
    102 rdf:type schema:CreativeWork
    103 https://www.grid.ac/institutes/grid.15781.3a schema:alternateName Paul Sabatier University
    104 schema:name IRIT, University of Toulouse III, 31062 Toulouse, France
    105 rdf:type schema:Organization
    106 https://www.grid.ac/institutes/grid.462878.7 schema:alternateName Laboratoire des Sciences de l'Information et des Systèmes
    107 schema:name LSIS, Aix-Marseille University, 13397 Marseille, France
    108 rdf:type schema:Organization
    109 https://www.grid.ac/institutes/grid.463910.9 schema:alternateName Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
    110 schema:name GREYC, University of Caen Basse-Normandie, 14032 Caen, France
    111 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...