A Dynamic location problem for graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1989-06

AUTHORS

F. R. K. Chung, R. L. Graham, M. E. Saks

ABSTRACT

We introduce a class of optimization problems, calleddynamic location problems, involving the processing of requests that occur sequentially at the nodes of a graphG. This leads to the definition of a new parameter of graphs, called the window indexWX(G), that measures how large a “window” into the future is needed to solve every instance of the dynamic location problem onG optimally on-line. We completely characterize this parameter:WX(G)≦k if and only ifG is a weak retract of a product of complete graphs of size at mostk. As a byproduct, we obtain two (polynomially recognizable) structural characterizations of such graphs, extending a result of Bandelt. More... »

PAGES

111-131

References to SciGraph publications

  • 1965-11. Isometric embedding of a graph in a Boolean cube in CYBERNETICS AND SYSTEMS ANALYSIS
  • 1974. Absolute retracts in graphs in GRAPHS AND COMBINATORICS
  • 1972. On embedding graphs in squashed cubes in GRAPH THEORY AND APPLICATIONS
  • 1982-03. On a class of isometric subgraphs of a graph in COMBINATORICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf02124674

    DOI

    http://dx.doi.org/10.1007/bf02124674

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Bell Communications Research Morristown, 07960, New Jersey, USA", 
              "id": "http://www.grid.ac/institutes/grid.432790.b", 
              "name": [
                "Bell Communications Research Morristown, 07960, New Jersey, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chung", 
            "givenName": "F. R. K.", 
            "id": "sg:person.013624262576.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624262576.00"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics and RUTCOR, Rutgers University New Brunswick, 08903, New Jersey, USA", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "AT&T Bell Laboratories Murray Hill, 07074, New Jersey, USA", 
                "Department of Mathematics and RUTCOR, Rutgers University New Brunswick, 08903, New Jersey, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Graham", 
            "givenName": "R. L.", 
            "id": "sg:person.011754654412.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011754654412.94"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics and RUTCOR, Rutgers University New Brunswick, 08903, New Jersey, USA", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Bell Communications Research Morristown, 07960, New Jersey, USA", 
                "Department of Mathematics and RUTCOR, Rutgers University New Brunswick, 08903, New Jersey, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Saks", 
            "givenName": "M. E.", 
            "id": "sg:person.011520224512.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02579284", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024534200", 
              "https://doi.org/10.1007/bf02579284"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0067362", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003888542", 
              "https://doi.org/10.1007/bfb0067362"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0066450", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026697773", 
              "https://doi.org/10.1007/bfb0066450"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01074705", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011748481", 
              "https://doi.org/10.1007/bf01074705"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1989-06", 
        "datePublishedReg": "1989-06-01", 
        "description": "We introduce a class of optimization problems, calleddynamic location problems, involving the processing of requests that occur sequentially at the nodes of a graphG. This leads to the definition of a new parameter of graphs, called the window indexWX(G), that measures how large a \u201cwindow\u201d into the future is needed to solve every instance of the dynamic location problem onG optimally on-line. We completely characterize this parameter:WX(G)\u2266k if and only ifG is a weak retract of a product of complete graphs of size at mostk. As a byproduct, we obtain two (polynomially recognizable) structural characterizations of such graphs, extending a result of Bandelt.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf02124674", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "9"
          }
        ], 
        "keywords": [
          "location problem", 
          "optimization problem", 
          "such graphs", 
          "complete graph", 
          "graph", 
          "dynamic location problem", 
          "problem", 
          "new parameter", 
          "Bandelt", 
          "processing of requests", 
          "parameters", 
          "graphG.", 
          "retract", 
          "mostk", 
          "class", 
          "Ong", 
          "nodes", 
          "instances", 
          "definition", 
          "window", 
          "results", 
          "size", 
          "structural characterization", 
          "lines", 
          "processing", 
          "byproducts", 
          "characterization", 
          "requests", 
          "IFG", 
          "products", 
          "future"
        ], 
        "name": "A Dynamic location problem for graphs", 
        "pagination": "111-131", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1028836326"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02124674"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02124674", 
          "https://app.dimensions.ai/details/publication/pub.1028836326"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-09-02T15:46", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_190.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf02124674"
      }
    ]
     

    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/bf02124674'

    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/bf02124674'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02124674'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02124674'


     

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

    123 TRIPLES      21 PREDICATES      60 URIs      48 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02124674 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N75368e6b30464dc7bb1c7419af43a649
    4 schema:citation sg:pub.10.1007/bf01074705
    5 sg:pub.10.1007/bf02579284
    6 sg:pub.10.1007/bfb0066450
    7 sg:pub.10.1007/bfb0067362
    8 schema:datePublished 1989-06
    9 schema:datePublishedReg 1989-06-01
    10 schema:description We introduce a class of optimization problems, calleddynamic location problems, involving the processing of requests that occur sequentially at the nodes of a graphG. This leads to the definition of a new parameter of graphs, called the window indexWX(G), that measures how large a “window” into the future is needed to solve every instance of the dynamic location problem onG optimally on-line. We completely characterize this parameter:WX(G)≦k if and only ifG is a weak retract of a product of complete graphs of size at mostk. As a byproduct, we obtain two (polynomially recognizable) structural characterizations of such graphs, extending a result of Bandelt.
    11 schema:genre article
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N7eb002c1ee814499b74a9bf72022bb3b
    14 Nc07392baf3f14294bf7973e73588702d
    15 sg:journal.1136493
    16 schema:keywords Bandelt
    17 IFG
    18 Ong
    19 byproducts
    20 characterization
    21 class
    22 complete graph
    23 definition
    24 dynamic location problem
    25 future
    26 graph
    27 graphG.
    28 instances
    29 lines
    30 location problem
    31 mostk
    32 new parameter
    33 nodes
    34 optimization problem
    35 parameters
    36 problem
    37 processing
    38 processing of requests
    39 products
    40 requests
    41 results
    42 retract
    43 size
    44 structural characterization
    45 such graphs
    46 window
    47 schema:name A Dynamic location problem for graphs
    48 schema:pagination 111-131
    49 schema:productId N1f73811657a7489ebb592d823981e5ba
    50 Naac6ee5214c24763bed1605b46e09fc0
    51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028836326
    52 https://doi.org/10.1007/bf02124674
    53 schema:sdDatePublished 2022-09-02T15:46
    54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    55 schema:sdPublisher N17c49335aad74751a2877cf5200b7007
    56 schema:url https://doi.org/10.1007/bf02124674
    57 sgo:license sg:explorer/license/
    58 sgo:sdDataset articles
    59 rdf:type schema:ScholarlyArticle
    60 N17c49335aad74751a2877cf5200b7007 schema:name Springer Nature - SN SciGraph project
    61 rdf:type schema:Organization
    62 N1f73811657a7489ebb592d823981e5ba schema:name doi
    63 schema:value 10.1007/bf02124674
    64 rdf:type schema:PropertyValue
    65 N2db94ebcd4fe4f0c86aeb76b51506072 rdf:first sg:person.011520224512.05
    66 rdf:rest rdf:nil
    67 N34e14f91238c499e9def254e9233dd2c rdf:first sg:person.011754654412.94
    68 rdf:rest N2db94ebcd4fe4f0c86aeb76b51506072
    69 N75368e6b30464dc7bb1c7419af43a649 rdf:first sg:person.013624262576.00
    70 rdf:rest N34e14f91238c499e9def254e9233dd2c
    71 N7eb002c1ee814499b74a9bf72022bb3b schema:issueNumber 2
    72 rdf:type schema:PublicationIssue
    73 Naac6ee5214c24763bed1605b46e09fc0 schema:name dimensions_id
    74 schema:value pub.1028836326
    75 rdf:type schema:PropertyValue
    76 Nc07392baf3f14294bf7973e73588702d schema:volumeNumber 9
    77 rdf:type schema:PublicationVolume
    78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Information and Computing Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Computation Theory and Mathematics
    83 rdf:type schema:DefinedTerm
    84 sg:journal.1136493 schema:issn 0209-9683
    85 1439-6912
    86 schema:name Combinatorica
    87 schema:publisher Springer Nature
    88 rdf:type schema:Periodical
    89 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
    90 schema:familyName Saks
    91 schema:givenName M. E.
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
    93 rdf:type schema:Person
    94 sg:person.011754654412.94 schema:affiliation grid-institutes:grid.430387.b
    95 schema:familyName Graham
    96 schema:givenName R. L.
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011754654412.94
    98 rdf:type schema:Person
    99 sg:person.013624262576.00 schema:affiliation grid-institutes:grid.432790.b
    100 schema:familyName Chung
    101 schema:givenName F. R. K.
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624262576.00
    103 rdf:type schema:Person
    104 sg:pub.10.1007/bf01074705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011748481
    105 https://doi.org/10.1007/bf01074705
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/bf02579284 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024534200
    108 https://doi.org/10.1007/bf02579284
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/bfb0066450 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026697773
    111 https://doi.org/10.1007/bfb0066450
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/bfb0067362 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003888542
    114 https://doi.org/10.1007/bfb0067362
    115 rdf:type schema:CreativeWork
    116 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics and RUTCOR, Rutgers University New Brunswick, 08903, New Jersey, USA
    117 schema:name AT&T Bell Laboratories Murray Hill, 07074, New Jersey, USA
    118 Bell Communications Research Morristown, 07960, New Jersey, USA
    119 Department of Mathematics and RUTCOR, Rutgers University New Brunswick, 08903, New Jersey, USA
    120 rdf:type schema:Organization
    121 grid-institutes:grid.432790.b schema:alternateName Bell Communications Research Morristown, 07960, New Jersey, USA
    122 schema:name Bell Communications Research Morristown, 07960, New Jersey, USA
    123 rdf:type schema:Organization
     




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


    ...