Stability of Reapproximation Algorithms for the β-Metric Traveling Salesman (Path) Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-08-09

AUTHORS

Annalisa D’Andrea , Luca Forlizzi , Guido Proietti

ABSTRACT

Inspired by the concept of stability of approximation, we consider the following (re)optimization problem: Given a minimum-cost Hamiltonian cycle of a complete non-negatively real weighted graph G=(V,E,c) obeying the strengthened triangle inequality (i.e., for some strength factor1/2≤β<1, we have that ∀u,v,z∈V,c(u,z)≤β(c(u,v)+c(v,z))), and given a vertex v whose removal from G (resp., addition to G), along with all its incident edges, produces a new weighted graph still obeying the strengthened triangle inequality, find a minimum-cost Hamiltonian cycle of the modified graph. This problem is known to be NP-hard, but we show that it admits a PTAS, which just consists of either returning the old optimal cycle (after having by-passed the removed node), or instead computing (for finitely many inputs) a new optimal solution from scratch − depending on the required accuracy in the approximation. Then, we turn our attention to the case in which a minimum-cost Hamiltonian path is given instead, and the underlying graph obeys the relaxed triangle inequality. Here, if one edge weight is increased, and , denotes the relaxation factor of the original and the modified graph, respectively, then we show how to obtain an approximation of , which improves over existing solutions as soon as . More... »

PAGES

156-171

References to SciGraph publications

  • 2005. On the Stability of Approximation for Hamiltonian Path Problems in SOFSEM 2005: THEORY AND PRACTICE OF COMPUTER SCIENCE
  • 2000. An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality in STACS 2000
  • 2002-04-19. Stability of Approximation Algorithms for Hard Optimization Problems in SOFSEM’99: THEORY AND PRACTICE OF INFORMATICS
  • 2002-07-18. Performance Guarantees for the TSP with a Parameterized Triangle Inequality in ALGORITHMS AND DATA STRUCTURES
  • 2006. Reoptimization of Minimum and Maximum Traveling Salesman’s Tours in ALGORITHM THEORY – SWAT 2006
  • 2012. Reoptimizing the Strengthened Metric TSP on Multiple Edge Weight Modifications in EXPERIMENTAL ALGORITHMS
  • 2012. New Advances in Reoptimizing the Minimum Steiner Tree Problem in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2012
  • 2008. Reoptimization of Steiner Trees in ALGORITHM THEORY – SWAT 2008
  • 2009. Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights in LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS
  • 2013. Eight-Fifth Approximation for the Path TSP in INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION
  • 2011-10. Approximating the Metric TSP in Linear Time in THEORY OF COMPUTING SYSTEMS
  • 2006. On the Approximation Hardness of Some Generalizations of TSP in ALGORITHM THEORY – SWAT 2006
  • 2007-10. The Parameterized Approximability of TSP with Deadlines in THEORY OF COMPUTING SYSTEMS
  • 1999. Stability of Approximation Algorithms and the Knapsack Problem in JEWELS ARE FOREVER
  • Book

    TITLE

    Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications

    ISBN

    978-3-319-12567-1
    978-3-319-12568-8

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-98355-4_10

    DOI

    http://dx.doi.org/10.1007/978-3-319-98355-4_10

    DIMENSIONS

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


    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/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of L'Aquila", 
              "id": "https://www.grid.ac/institutes/grid.158820.6", 
              "name": [
                "Dipartimento di Ingegneria e Scienze dell\u2019Informazione e Matematica, Universit\u00e0 degli Studi dell\u2019Aquila, Via Vetoio, 67100, L\u2019Aquila, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "D\u2019Andrea", 
            "givenName": "Annalisa", 
            "id": "sg:person.014732213025.38", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014732213025.38"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of L'Aquila", 
              "id": "https://www.grid.ac/institutes/grid.158820.6", 
              "name": [
                "Dipartimento di Ingegneria e Scienze dell\u2019Informazione e Matematica, Universit\u00e0 degli Studi dell\u2019Aquila, Via Vetoio, 67100, L\u2019Aquila, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Forlizzi", 
            "givenName": "Luca", 
            "id": "sg:person.012341045343.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012341045343.19"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti", 
              "id": "https://www.grid.ac/institutes/grid.419461.f", 
              "name": [
                "Dipartimento di Ingegneria e Scienze dell\u2019Informazione e Matematica, Universit\u00e0 degli Studi dell\u2019Aquila, Via Vetoio, 67100, L\u2019Aquila, Italy", 
                "Istituto di Analisi dei Sistemi ed Informatica \u201cAntonio Ruberti\u201d, Consiglio Nazionale delle Ricerche, Via dei Taurini 19, 00185, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Proietti", 
            "givenName": "Guido", 
            "id": "sg:person.015510625760.85", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015510625760.85"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s00224-007-1347-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000278583", 
              "https://doi.org/10.1007/s00224-007-1347-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jda.2011.03.014", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006216721"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-47849-3_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006635617", 
              "https://doi.org/10.1007/3-540-47849-3_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-47849-3_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006635617", 
              "https://doi.org/10.1007/3-540-47849-3_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-010-9289-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006868240", 
              "https://doi.org/10.1007/s00224-010-9289-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-00982-2_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007783888", 
              "https://doi.org/10.1007/978-3-642-00982-2_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-00982-2_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007783888", 
              "https://doi.org/10.1007/978-3-642-00982-2_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30577-4_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011521688", 
              "https://doi.org/10.1007/978-3-540-30577-4_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2008.04.039", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013341213"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-69903-3_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015248639", 
              "https://doi.org/10.1007/978-3-540-69903-3_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11785293_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022568163", 
              "https://doi.org/10.1007/11785293_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11785293_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022568163", 
              "https://doi.org/10.1007/11785293_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-36694-9_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028567541", 
              "https://doi.org/10.1007/978-3-642-36694-9_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-32589-2_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030219546", 
              "https://doi.org/10.1007/978-3-642-32589-2_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jda.2008.03.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031528368"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.10091", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034729802"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jda.2009.04.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034962026"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0020-0190(00)00089-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036526159"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(01)00287-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037255787"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(01)00287-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037255787"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-30850-5_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037340829", 
              "https://doi.org/10.1007/978-3-642-30850-5_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48447-7_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038686412", 
              "https://doi.org/10.1007/3-540-48447-7_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48447-7_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038686412", 
              "https://doi.org/10.1007/3-540-48447-7_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2009.02.016", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042119159"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.1024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043476044"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46541-3_32", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045663849", 
              "https://doi.org/10.1007/3-540-46541-3_32"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2004.06.019", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047269567"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11785293_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049044468", 
              "https://doi.org/10.1007/11785293_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11785293_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049044468", 
              "https://doi.org/10.1007/11785293_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-60207-8_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049893243", 
              "https://doi.org/10.1007/978-3-642-60207-8_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-60207-8_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049893243", 
              "https://doi.org/10.1007/978-3-642-60207-8_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1051/ita:2000115", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1056972075"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0206041", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841380"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0895480192240226", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062882886"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-08-09", 
        "datePublishedReg": "2018-08-09", 
        "description": "Inspired by the concept of stability of approximation, we consider the following (re)optimization problem: Given a minimum-cost Hamiltonian cycle of a complete non-negatively real weighted graph G=(V,E,c) obeying the strengthened triangle inequality (i.e., for some strength factor1/2\u2264\u03b2<1, we have that \u2200u,v,z\u2208V,c(u,z)\u2264\u03b2(c(u,v)+c(v,z))), and given a vertex v whose removal from G (resp., addition to G), along with all its incident edges, produces a new weighted graph still obeying the strengthened triangle inequality, find a minimum-cost Hamiltonian cycle of the modified graph. This problem is known to be NP-hard, but we show that it admits a PTAS, which just consists of either returning the old optimal cycle (after having by-passed the removed node), or instead computing (for finitely many inputs) a new optimal solution from scratch \u2212 depending on the required accuracy in the approximation. Then, we turn our attention to the case in which a minimum-cost Hamiltonian path is given instead, and the underlying graph obeys the relaxed triangle inequality. Here, if one edge weight is increased, and , denotes the relaxation factor of the original and the modified graph, respectively, then we show how to obtain an approximation of , which improves over existing solutions as soon as .", 
        "editor": [
          {
            "familyName": "Bayro-Corrochano", 
            "givenName": "Eduardo", 
            "type": "Person"
          }, 
          {
            "familyName": "Hancock", 
            "givenName": "Edwin", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-98355-4_10", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-319-12567-1", 
            "978-3-319-12568-8"
          ], 
          "name": "Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications", 
          "type": "Book"
        }, 
        "name": "Stability of Reapproximation Algorithms for the \u03b2-Metric Traveling Salesman (Path) Problem", 
        "pagination": "156-171", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-98355-4_10"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "af43a200daf37dd2c861510ebba6f11f87856b4bb9049f2091da1c19c7d07502"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1106070113"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-98355-4_10", 
          "https://app.dimensions.ai/details/publication/pub.1106070113"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:00", 
        "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/0000000325_0000000325/records_100791_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-319-98355-4_10"
      }
    ]
     

    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-98355-4_10'

    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-98355-4_10'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98355-4_10'

    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-98355-4_10'


     

    This table displays all metadata directly associated to this object as RDF triples.

    183 TRIPLES      23 PREDICATES      53 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-98355-4_10 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author N09ce0306348e430983959718a70650d0
    4 schema:citation sg:pub.10.1007/11785293_19
    5 sg:pub.10.1007/11785293_20
    6 sg:pub.10.1007/3-540-46541-3_32
    7 sg:pub.10.1007/3-540-47849-3_2
    8 sg:pub.10.1007/3-540-48447-7_10
    9 sg:pub.10.1007/978-3-540-30577-4_18
    10 sg:pub.10.1007/978-3-540-69903-3_24
    11 sg:pub.10.1007/978-3-642-00982-2_12
    12 sg:pub.10.1007/978-3-642-30850-5_11
    13 sg:pub.10.1007/978-3-642-32589-2_19
    14 sg:pub.10.1007/978-3-642-36694-9_31
    15 sg:pub.10.1007/978-3-642-60207-8_21
    16 sg:pub.10.1007/s00224-007-1347-x
    17 sg:pub.10.1007/s00224-010-9289-0
    18 https://doi.org/10.1002/net.10091
    19 https://doi.org/10.1002/net.1024
    20 https://doi.org/10.1016/j.jda.2008.03.003
    21 https://doi.org/10.1016/j.jda.2009.04.001
    22 https://doi.org/10.1016/j.jda.2011.03.014
    23 https://doi.org/10.1016/j.tcs.2004.06.019
    24 https://doi.org/10.1016/j.tcs.2008.04.039
    25 https://doi.org/10.1016/j.tcs.2009.02.016
    26 https://doi.org/10.1016/s0020-0190(00)00089-2
    27 https://doi.org/10.1016/s0304-3975(01)00287-0
    28 https://doi.org/10.1051/ita:2000115
    29 https://doi.org/10.1137/0206041
    30 https://doi.org/10.1137/s0895480192240226
    31 schema:datePublished 2018-08-09
    32 schema:datePublishedReg 2018-08-09
    33 schema:description Inspired by the concept of stability of approximation, we consider the following (re)optimization problem: Given a minimum-cost Hamiltonian cycle of a complete non-negatively real weighted graph G=(V,E,c) obeying the strengthened triangle inequality (i.e., for some strength factor1/2≤β<1, we have that ∀u,v,z∈V,c(u,z)≤β(c(u,v)+c(v,z))), and given a vertex v whose removal from G (resp., addition to G), along with all its incident edges, produces a new weighted graph still obeying the strengthened triangle inequality, find a minimum-cost Hamiltonian cycle of the modified graph. This problem is known to be NP-hard, but we show that it admits a PTAS, which just consists of either returning the old optimal cycle (after having by-passed the removed node), or instead computing (for finitely many inputs) a new optimal solution from scratch − depending on the required accuracy in the approximation. Then, we turn our attention to the case in which a minimum-cost Hamiltonian path is given instead, and the underlying graph obeys the relaxed triangle inequality. Here, if one edge weight is increased, and , denotes the relaxation factor of the original and the modified graph, respectively, then we show how to obtain an approximation of , which improves over existing solutions as soon as .
    34 schema:editor Ncd6f0c0f07fa4d9394a21b14bb13d461
    35 schema:genre chapter
    36 schema:inLanguage en
    37 schema:isAccessibleForFree false
    38 schema:isPartOf N9dc2c2b4f74a4e0194c6a24ff14dd58f
    39 schema:name Stability of Reapproximation Algorithms for the β-Metric Traveling Salesman (Path) Problem
    40 schema:pagination 156-171
    41 schema:productId N5a62abd7dfe44139b584887f5cc7f284
    42 N91b2d59ffaf54462a5f6ed17f57b980a
    43 Ne118668d684242639caa6d590076de0a
    44 schema:publisher N235a63688d354b40b2b20ddb08dba59e
    45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106070113
    46 https://doi.org/10.1007/978-3-319-98355-4_10
    47 schema:sdDatePublished 2019-04-16T05:00
    48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    49 schema:sdPublisher Nd7fcc180b337466aab61304eb5fd8cb9
    50 schema:url https://link.springer.com/10.1007%2F978-3-319-98355-4_10
    51 sgo:license sg:explorer/license/
    52 sgo:sdDataset chapters
    53 rdf:type schema:Chapter
    54 N09ce0306348e430983959718a70650d0 rdf:first sg:person.014732213025.38
    55 rdf:rest N3e8a2b022fcc47b6bf10869552ce7971
    56 N235a63688d354b40b2b20ddb08dba59e schema:location Cham
    57 schema:name Springer International Publishing
    58 rdf:type schema:Organisation
    59 N3e8a2b022fcc47b6bf10869552ce7971 rdf:first sg:person.012341045343.19
    60 rdf:rest N5cf859e9aaaa4e8b834706dbf308d7a0
    61 N5a62abd7dfe44139b584887f5cc7f284 schema:name dimensions_id
    62 schema:value pub.1106070113
    63 rdf:type schema:PropertyValue
    64 N5cf859e9aaaa4e8b834706dbf308d7a0 rdf:first sg:person.015510625760.85
    65 rdf:rest rdf:nil
    66 N91b2d59ffaf54462a5f6ed17f57b980a schema:name readcube_id
    67 schema:value af43a200daf37dd2c861510ebba6f11f87856b4bb9049f2091da1c19c7d07502
    68 rdf:type schema:PropertyValue
    69 N92bc6d5e85134f5e9e18b87e778c20bb schema:familyName Bayro-Corrochano
    70 schema:givenName Eduardo
    71 rdf:type schema:Person
    72 N9dc2c2b4f74a4e0194c6a24ff14dd58f schema:isbn 978-3-319-12567-1
    73 978-3-319-12568-8
    74 schema:name Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications
    75 rdf:type schema:Book
    76 Ncd6f0c0f07fa4d9394a21b14bb13d461 rdf:first N92bc6d5e85134f5e9e18b87e778c20bb
    77 rdf:rest Nf41385af96334ffbac5530acd15cdc5b
    78 Nd7fcc180b337466aab61304eb5fd8cb9 schema:name Springer Nature - SN SciGraph project
    79 rdf:type schema:Organization
    80 Ne118668d684242639caa6d590076de0a schema:name doi
    81 schema:value 10.1007/978-3-319-98355-4_10
    82 rdf:type schema:PropertyValue
    83 Nf41385af96334ffbac5530acd15cdc5b rdf:first Nf505a1b9af4a439ba625e100c0c66518
    84 rdf:rest rdf:nil
    85 Nf505a1b9af4a439ba625e100c0c66518 schema:familyName Hancock
    86 schema:givenName Edwin
    87 rdf:type schema:Person
    88 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Mathematical Sciences
    90 rdf:type schema:DefinedTerm
    91 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Numerical and Computational Mathematics
    93 rdf:type schema:DefinedTerm
    94 sg:person.012341045343.19 schema:affiliation https://www.grid.ac/institutes/grid.158820.6
    95 schema:familyName Forlizzi
    96 schema:givenName Luca
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012341045343.19
    98 rdf:type schema:Person
    99 sg:person.014732213025.38 schema:affiliation https://www.grid.ac/institutes/grid.158820.6
    100 schema:familyName D’Andrea
    101 schema:givenName Annalisa
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014732213025.38
    103 rdf:type schema:Person
    104 sg:person.015510625760.85 schema:affiliation https://www.grid.ac/institutes/grid.419461.f
    105 schema:familyName Proietti
    106 schema:givenName Guido
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015510625760.85
    108 rdf:type schema:Person
    109 sg:pub.10.1007/11785293_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049044468
    110 https://doi.org/10.1007/11785293_19
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/11785293_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022568163
    113 https://doi.org/10.1007/11785293_20
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/3-540-46541-3_32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045663849
    116 https://doi.org/10.1007/3-540-46541-3_32
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/3-540-47849-3_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006635617
    119 https://doi.org/10.1007/3-540-47849-3_2
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/3-540-48447-7_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038686412
    122 https://doi.org/10.1007/3-540-48447-7_10
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-3-540-30577-4_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011521688
    125 https://doi.org/10.1007/978-3-540-30577-4_18
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/978-3-540-69903-3_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015248639
    128 https://doi.org/10.1007/978-3-540-69903-3_24
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/978-3-642-00982-2_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007783888
    131 https://doi.org/10.1007/978-3-642-00982-2_12
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/978-3-642-30850-5_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037340829
    134 https://doi.org/10.1007/978-3-642-30850-5_11
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/978-3-642-32589-2_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030219546
    137 https://doi.org/10.1007/978-3-642-32589-2_19
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/978-3-642-36694-9_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028567541
    140 https://doi.org/10.1007/978-3-642-36694-9_31
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/978-3-642-60207-8_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049893243
    143 https://doi.org/10.1007/978-3-642-60207-8_21
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/s00224-007-1347-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1000278583
    146 https://doi.org/10.1007/s00224-007-1347-x
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/s00224-010-9289-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006868240
    149 https://doi.org/10.1007/s00224-010-9289-0
    150 rdf:type schema:CreativeWork
    151 https://doi.org/10.1002/net.10091 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034729802
    152 rdf:type schema:CreativeWork
    153 https://doi.org/10.1002/net.1024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043476044
    154 rdf:type schema:CreativeWork
    155 https://doi.org/10.1016/j.jda.2008.03.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031528368
    156 rdf:type schema:CreativeWork
    157 https://doi.org/10.1016/j.jda.2009.04.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034962026
    158 rdf:type schema:CreativeWork
    159 https://doi.org/10.1016/j.jda.2011.03.014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006216721
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.1016/j.tcs.2004.06.019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047269567
    162 rdf:type schema:CreativeWork
    163 https://doi.org/10.1016/j.tcs.2008.04.039 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013341213
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1016/j.tcs.2009.02.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042119159
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1016/s0020-0190(00)00089-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036526159
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1016/s0304-3975(01)00287-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037255787
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1051/ita:2000115 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056972075
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1137/0206041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841380
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1137/s0895480192240226 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882886
    176 rdf:type schema:CreativeWork
    177 https://www.grid.ac/institutes/grid.158820.6 schema:alternateName University of L'Aquila
    178 schema:name Dipartimento di Ingegneria e Scienze dell’Informazione e Matematica, Università degli Studi dell’Aquila, Via Vetoio, 67100, L’Aquila, Italy
    179 rdf:type schema:Organization
    180 https://www.grid.ac/institutes/grid.419461.f schema:alternateName Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti
    181 schema:name Dipartimento di Ingegneria e Scienze dell’Informazione e Matematica, Università degli Studi dell’Aquila, Via Vetoio, 67100, L’Aquila, Italy
    182 Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti”, Consiglio Nazionale delle Ricerche, Via dei Taurini 19, 00185, Rome, Italy
    183 rdf:type schema:Organization
     




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


    ...