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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fukuyama", 
        "givenName": "Junichiro", 
        "id": "sg:person.015266205731.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015266205731.31"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-08-17", 
    "datePublishedReg": "2001-08-17", 
    "description": "The Postman Problem is defined in the following manner: Given a connected graph G and a start point s \u03c4 V(G), we call a path J in G a postman tour if J starts and ends at s and contains every edge in E(G). We want to find a shortest postman tour in G. Thus, we minimize the number |J| - |E(G)|, called the penalty of J for G. In this paper, we consider two online versions of The Postman Problem, in which the postman is initially placed at a start point and allowed to move on edges. The postman is given information on the incident edges and/or the adjacent vertices of the current vertex v. The first model is called The Labyrinth Model, where the postman only knows the existence of the incident edges from v. Thus, he/she does not know the other endpoint w of an edge from v, even if it is already visited. The second one is The Corridor Model, where the postman can \u2018see\u2019 the other endpoint w from v. This means that if w is already visited, he/she knows the existence of w before traversing the edge (v,w). We devised an algorithm for The Corridor Model whose penalty is bounded by 2| V(G)| - 2. It performs better than the algorithm described in [8], in the case when the other visited endpoint of an edge from a current vertex is known to the postman. In addition, we obtained lower bounds of a penalty for The Corridor and Labyrinth Models. They are (4|V(G)|-5)/3 and (5|V(G)| -3)/4, respectively. Our online algorithm uses a linear time algorithm for the offline Postman Problem with a penalty at most |V| - 1. Thus, the minimum penalty does not exceed |V| - 1 for every connected graph G. This is the first known upper bound of a penalty of an offline postman tour, and matches the obvious lower bound exactly.", 
    "editor": [
      {
        "familyName": "Goemans", 
        "givenName": "Michel", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Trevisan", 
        "givenName": "Luca", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44666-4_9", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42470-3", 
        "978-3-540-44666-8"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "postman problem", 
      "postman tour", 
      "linear time algorithm", 
      "shortest postman tour", 
      "online algorithm", 
      "lower bounds", 
      "current vertex", 
      "graph G.", 
      "adjacent vertices", 
      "connected graph G", 
      "graph G", 
      "incident edges", 
      "time algorithm", 
      "corridor model", 
      "connected graph G.", 
      "vertex v.", 
      "first model", 
      "algorithm", 
      "vertices", 
      "problem", 
      "second one", 
      "small penalty", 
      "existence", 
      "bounds", 
      "edge", 
      "model", 
      "minimum penalty", 
      "penalty", 
      "G.", 
      "version", 
      "following manner", 
      "point", 
      "one", 
      "start point", 
      "number", 
      "Postman", 
      "cases", 
      "tour", 
      "online version", 
      "information", 
      "incidents", 
      "manner", 
      "v.", 
      "corridor", 
      "addition", 
      "endpoint", 
      "paper"
    ], 
    "name": "An Online Algorithm for the Postman Problem with a Small Penalty", 
    "pagination": "48-54", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011915729"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44666-4_9"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44666-4_9", 
      "https://app.dimensions.ai/details/publication/pub.1011915729"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:22", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_452.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44666-4_9"
  }
]

Download the RDF metadata as:  json-ld nt turtle xml License info

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

128 TRIPLES      22 PREDICATES      71 URIs      64 LITERALS      7 BLANK NODES