Exploration of Periodically Varying Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Paola Flocchini , Bernard Mans , Nicola Santoro

ABSTRACT

We study the computability and complexity of the exploration problem in a class of highly dynamic graphs: periodically varying (PV) graphs, where the edges exist only at some (unknown) times defined by the periodic movements of carriers. These graphs naturally model highly dynamic infrastructure-less networks such as public transports with fixed timetables, low earth orbiting (LEO) satellite systems, security guards’ tours, etc. We establish necessary conditions for the problem to be solved. We also derive lower bounds on the amount of time required in general, as well as for the PV graphs defined by restricted classes of carriers movements: simple routes, and circular routes. We then prove that the limitations on computability and complexity we have established are indeed tight. We do so constructively presenting two worst case optimal solution algorithms, one for anonymous systems, and one for those with distinct nodes ids. More... »

PAGES

534-543

References to SciGraph publications

Book

TITLE

Algorithms and Computation

ISBN

978-3-642-10630-9
978-3-642-10631-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_55

DOI

http://dx.doi.org/10.1007/978-3-642-10631-6_55

DIMENSIONS

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


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": "University of Ottawa", 
          "id": "https://www.grid.ac/institutes/grid.28046.38", 
          "name": [
            "University of Ottawa, Ottawa, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Flocchini", 
        "givenName": "Paola", 
        "id": "sg:person.011601470625.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Macquarie University", 
          "id": "https://www.grid.ac/institutes/grid.1004.5", 
          "name": [
            "Macquarie University, Sydney, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mans", 
        "givenName": "Bernard", 
        "id": "sg:person.010123221175.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010123221175.95"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Carleton University", 
          "id": "https://www.grid.ac/institutes/grid.34428.39", 
          "name": [
            "Carleton University, Ottawa, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Santoro", 
        "givenName": "Nicola", 
        "id": "sg:person.010566557723.84", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/j.tcs.2004.07.031", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001736746"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1080139.1080143", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003349339"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010742782"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1287853.1287876", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023827035"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-70575-8_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027002019", 
          "https://doi.org/10.1007/978-3-540-70575-8_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1383369.1383373", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028971713"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/inco.2001.3081", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052134892"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tpds.2008.218", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061753328"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s009753979732428x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880193"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/infcom.2009.5061927", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094368164"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We study the computability and complexity of the exploration problem in a class of highly dynamic graphs: periodically varying (PV) graphs, where the edges exist only at some (unknown) times defined by the periodic movements of carriers. These graphs naturally model highly dynamic infrastructure-less networks such as public transports with fixed timetables, low earth orbiting (LEO) satellite systems, security guards\u2019 tours, etc. We establish necessary conditions for the problem to be solved. We also derive lower bounds on the amount of time required in general, as well as for the PV graphs defined by restricted classes of carriers movements: simple routes, and circular routes. We then prove that the limitations on computability and complexity we have established are indeed tight. We do so constructively presenting two worst case optimal solution algorithms, one for anonymous systems, and one for those with distinct nodes ids.", 
    "editor": [
      {
        "familyName": "Dong", 
        "givenName": "Yingfei", 
        "type": "Person"
      }, 
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Ibarra", 
        "givenName": "Oscar", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-10631-6_55", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-10630-9", 
        "978-3-642-10631-6"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "name": "Exploration of Periodically Varying Graphs", 
    "pagination": "534-543", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1002089179"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-10631-6_55"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "09f30135d40e8f930dc8e158b532eca62639f7761cd48b26f367159f57276709"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-10631-6_55", 
      "https://app.dimensions.ai/details/publication/pub.1002089179"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07: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/0000000355_0000000355/records_53019_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-10631-6_55"
  }
]
 

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-642-10631-6_55'

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-642-10631-6_55'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_55'

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-642-10631-6_55'


 

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

126 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-10631-6_55 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nb8c6a950f32446998c97f4a32ed10e81
4 schema:citation sg:pub.10.1007/978-3-540-70575-8_11
5 https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8
6 https://doi.org/10.1006/inco.2001.3081
7 https://doi.org/10.1016/j.tcs.2004.07.031
8 https://doi.org/10.1109/infcom.2009.5061927
9 https://doi.org/10.1109/tpds.2008.218
10 https://doi.org/10.1137/s009753979732428x
11 https://doi.org/10.1145/1080139.1080143
12 https://doi.org/10.1145/1287853.1287876
13 https://doi.org/10.1145/1383369.1383373
14 schema:datePublished 2009
15 schema:datePublishedReg 2009-01-01
16 schema:description We study the computability and complexity of the exploration problem in a class of highly dynamic graphs: periodically varying (PV) graphs, where the edges exist only at some (unknown) times defined by the periodic movements of carriers. These graphs naturally model highly dynamic infrastructure-less networks such as public transports with fixed timetables, low earth orbiting (LEO) satellite systems, security guards’ tours, etc. We establish necessary conditions for the problem to be solved. We also derive lower bounds on the amount of time required in general, as well as for the PV graphs defined by restricted classes of carriers movements: simple routes, and circular routes. We then prove that the limitations on computability and complexity we have established are indeed tight. We do so constructively presenting two worst case optimal solution algorithms, one for anonymous systems, and one for those with distinct nodes ids.
17 schema:editor Nd3e17ca462374ec295a946dd17dfe186
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf Nb64f92bb751843488bdaf4f11568b958
22 schema:name Exploration of Periodically Varying Graphs
23 schema:pagination 534-543
24 schema:productId N7cc7f15153174320a28ce89945a8a837
25 N91c8ef96ebc5439d99e91d5aed47a128
26 Ne27e6ab1236a481d86267ffea7b22990
27 schema:publisher Na8a0c15bef3b4f64bdae4a7e55ac2880
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002089179
29 https://doi.org/10.1007/978-3-642-10631-6_55
30 schema:sdDatePublished 2019-04-16T07:27
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher Nf3cbf192163c4b34ae2e8c667b7a46e8
33 schema:url https://link.springer.com/10.1007%2F978-3-642-10631-6_55
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N047475d0c5b140e0ac02810411a86e9e schema:familyName Ibarra
38 schema:givenName Oscar
39 rdf:type schema:Person
40 N1ad60700b8e34a9faa15e25dec2ff9ac rdf:first sg:person.010566557723.84
41 rdf:rest rdf:nil
42 N5cbd78b5ee5b4900b337e7afcb0125cf rdf:first N047475d0c5b140e0ac02810411a86e9e
43 rdf:rest rdf:nil
44 N7cc7f15153174320a28ce89945a8a837 schema:name readcube_id
45 schema:value 09f30135d40e8f930dc8e158b532eca62639f7761cd48b26f367159f57276709
46 rdf:type schema:PropertyValue
47 N89694b76e0d94c55aa271e4029815f6c schema:familyName Dong
48 schema:givenName Yingfei
49 rdf:type schema:Person
50 N91c8ef96ebc5439d99e91d5aed47a128 schema:name doi
51 schema:value 10.1007/978-3-642-10631-6_55
52 rdf:type schema:PropertyValue
53 N9926dba80b624c3ca997f12f4a99c439 rdf:first sg:person.010123221175.95
54 rdf:rest N1ad60700b8e34a9faa15e25dec2ff9ac
55 Na8a0c15bef3b4f64bdae4a7e55ac2880 schema:location Berlin, Heidelberg
56 schema:name Springer Berlin Heidelberg
57 rdf:type schema:Organisation
58 Nb64f92bb751843488bdaf4f11568b958 schema:isbn 978-3-642-10630-9
59 978-3-642-10631-6
60 schema:name Algorithms and Computation
61 rdf:type schema:Book
62 Nb7ce92c0f6bd489f876bba5eefdaa4ef schema:familyName Du
63 schema:givenName Ding-Zhu
64 rdf:type schema:Person
65 Nb8c6a950f32446998c97f4a32ed10e81 rdf:first sg:person.011601470625.25
66 rdf:rest N9926dba80b624c3ca997f12f4a99c439
67 Nbacacd9308624581a10819b0627bc650 rdf:first Nb7ce92c0f6bd489f876bba5eefdaa4ef
68 rdf:rest N5cbd78b5ee5b4900b337e7afcb0125cf
69 Nd3e17ca462374ec295a946dd17dfe186 rdf:first N89694b76e0d94c55aa271e4029815f6c
70 rdf:rest Nbacacd9308624581a10819b0627bc650
71 Ne27e6ab1236a481d86267ffea7b22990 schema:name dimensions_id
72 schema:value pub.1002089179
73 rdf:type schema:PropertyValue
74 Nf3cbf192163c4b34ae2e8c667b7a46e8 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
80 schema:name Computation Theory and Mathematics
81 rdf:type schema:DefinedTerm
82 sg:person.010123221175.95 schema:affiliation https://www.grid.ac/institutes/grid.1004.5
83 schema:familyName Mans
84 schema:givenName Bernard
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010123221175.95
86 rdf:type schema:Person
87 sg:person.010566557723.84 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
88 schema:familyName Santoro
89 schema:givenName Nicola
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84
91 rdf:type schema:Person
92 sg:person.011601470625.25 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
93 schema:familyName Flocchini
94 schema:givenName Paola
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25
96 rdf:type schema:Person
97 sg:pub.10.1007/978-3-540-70575-8_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027002019
98 https://doi.org/10.1007/978-3-540-70575-8_11
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010742782
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1006/inco.2001.3081 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052134892
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/j.tcs.2004.07.031 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001736746
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1109/infcom.2009.5061927 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094368164
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1109/tpds.2008.218 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061753328
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1137/s009753979732428x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880193
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1145/1080139.1080143 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003349339
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1145/1287853.1287876 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023827035
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1145/1383369.1383373 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028971713
117 rdf:type schema:CreativeWork
118 https://www.grid.ac/institutes/grid.1004.5 schema:alternateName Macquarie University
119 schema:name Macquarie University, Sydney, Australia
120 rdf:type schema:Organization
121 https://www.grid.ac/institutes/grid.28046.38 schema:alternateName University of Ottawa
122 schema:name University of Ottawa, Ottawa, Canada
123 rdf:type schema:Organization
124 https://www.grid.ac/institutes/grid.34428.39 schema:alternateName Carleton University
125 schema:name Carleton University, Ottawa, Canada
126 rdf:type schema:Organization
 




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


...