Online Graph Exploration: New Results on Old and New Algorithms View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Nicole Megow , Kurt Mehlhorn , Pascal Schweitzer

ABSTRACT

We study the problem of exploring an unknown undirected connected graph. Beginning in some start vertex, a searcher must visit each node of the graph by traversing edges. Upon visiting a vertex for the first time, the searcher learns all incident edges and their respective traversal costs. The goal is to find a tour of minimum total cost. Kalyanasundaram and Pruhs [23] proposed a sophisticated generalization of a Depth First Search that is 16-competitive on planar graphs. While the algorithm is feasible on arbitrary graphs, the question whether it has constant competitive ratio in general has remained open. Our main result is an involved lower bound construction that answers this question negatively. On the positive side, we prove that the algorithm has constant competitive ratio on any class of graphs with bounded genus. Furthermore, we provide a constant competitive algorithm for general graphs with a bounded number of distinct weights. More... »

PAGES

478-489

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22012-8_38

DOI

http://dx.doi.org/10.1007/978-3-642-22012-8_38

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Megow", 
        "givenName": "Nicole", 
        "id": "sg:person.011513671015.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011513671015.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "The Australian National University, Canberra, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1001.0", 
          "name": [
            "The Australian National University, Canberra, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schweitzer", 
        "givenName": "Pascal", 
        "id": "sg:person.010731762606.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010731762606.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "We study the problem of exploring an unknown undirected connected graph. Beginning in some start vertex, a searcher must visit each node of the graph by traversing edges. Upon visiting a vertex for the first time, the searcher learns all incident edges and their respective traversal costs. The goal is to find a tour of minimum total cost. Kalyanasundaram and Pruhs [23] proposed a sophisticated generalization of a Depth First Search that is\u00a016-competitive on planar graphs. While the algorithm is feasible on arbitrary graphs, the question whether it has constant competitive ratio in general has remained open. Our main result is an involved lower bound construction that answers this question negatively. On the positive side, we prove that the algorithm has constant competitive ratio on any class of graphs with bounded genus. Furthermore, we provide a constant competitive algorithm for general graphs with a bounded number of distinct weights.", 
    "editor": [
      {
        "familyName": "Aceto", 
        "givenName": "Luca", 
        "type": "Person"
      }, 
      {
        "familyName": "Henzinger", 
        "givenName": "Monika", 
        "type": "Person"
      }, 
      {
        "familyName": "Sgall", 
        "givenName": "Ji\u0159\u00ed", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22012-8_38", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22011-1", 
        "978-3-642-22012-8"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "constant competitive ratio", 
      "depth-first search", 
      "competitive ratio", 
      "traversal cost", 
      "constant competitive algorithm", 
      "undirected connected graph", 
      "start vertex", 
      "first search", 
      "competitive algorithm", 
      "general graphs", 
      "bounded number", 
      "graph", 
      "algorithm", 
      "arbitrary graphs", 
      "new algorithm", 
      "searchers", 
      "minimum total cost", 
      "planar graphs", 
      "class of graphs", 
      "connected graph", 
      "distinct weights", 
      "vertices", 
      "nodes", 
      "cost", 
      "positive side", 
      "incident edges", 
      "total cost", 
      "Kalyanasundaram", 
      "Pruhs", 
      "edge", 
      "search", 
      "goal", 
      "tour", 
      "generalization", 
      "results", 
      "construction", 
      "class", 
      "time", 
      "number", 
      "questions", 
      "main results", 
      "new results", 
      "sophisticated generalization", 
      "first time", 
      "side", 
      "weight", 
      "problem", 
      "ratio", 
      "genus", 
      "olds"
    ], 
    "name": "Online Graph Exploration: New Results on Old and New Algorithms", 
    "pagination": "478-489", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011131440"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22012-8_38"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22012-8_38", 
      "https://app.dimensions.ai/details/publication/pub.1011131440"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:58", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_39.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22012-8_38"
  }
]
 

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-22012-8_38'

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-22012-8_38'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22012-8_38'

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-22012-8_38'


 

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

136 TRIPLES      22 PREDICATES      75 URIs      68 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22012-8_38 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N724e67dfed4245cbb85704165bbc71de
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description We study the problem of exploring an unknown undirected connected graph. Beginning in some start vertex, a searcher must visit each node of the graph by traversing edges. Upon visiting a vertex for the first time, the searcher learns all incident edges and their respective traversal costs. The goal is to find a tour of minimum total cost. Kalyanasundaram and Pruhs [23] proposed a sophisticated generalization of a Depth First Search that is 16-competitive on planar graphs. While the algorithm is feasible on arbitrary graphs, the question whether it has constant competitive ratio in general has remained open. Our main result is an involved lower bound construction that answers this question negatively. On the positive side, we prove that the algorithm has constant competitive ratio on any class of graphs with bounded genus. Furthermore, we provide a constant competitive algorithm for general graphs with a bounded number of distinct weights.
7 schema:editor N6e6e47acbf7b4e68b6b0ba235970fa20
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nc1b7d400121845f3a16d5ed79ba3aff3
11 schema:keywords Kalyanasundaram
12 Pruhs
13 algorithm
14 arbitrary graphs
15 bounded number
16 class
17 class of graphs
18 competitive algorithm
19 competitive ratio
20 connected graph
21 constant competitive algorithm
22 constant competitive ratio
23 construction
24 cost
25 depth-first search
26 distinct weights
27 edge
28 first search
29 first time
30 general graphs
31 generalization
32 genus
33 goal
34 graph
35 incident edges
36 main results
37 minimum total cost
38 new algorithm
39 new results
40 nodes
41 number
42 olds
43 planar graphs
44 positive side
45 problem
46 questions
47 ratio
48 results
49 search
50 searchers
51 side
52 sophisticated generalization
53 start vertex
54 time
55 total cost
56 tour
57 traversal cost
58 undirected connected graph
59 vertices
60 weight
61 schema:name Online Graph Exploration: New Results on Old and New Algorithms
62 schema:pagination 478-489
63 schema:productId N540f8ef7140e4b6cadc4f93d99e1e782
64 Ncf8c78371836410ebc0c9b23c815e56e
65 schema:publisher Nf41b5bd1d23947c9b8d05f2cf7b9b642
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011131440
67 https://doi.org/10.1007/978-3-642-22012-8_38
68 schema:sdDatePublished 2022-10-01T06:58
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher N4b687b588da1434abee8c7b35ad08b64
71 schema:url https://doi.org/10.1007/978-3-642-22012-8_38
72 sgo:license sg:explorer/license/
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N01b5ec9560f1487ca8b4102e1d11c4bb rdf:first N79d01b08bbfa403cbca4ba21d3dfc677
76 rdf:rest rdf:nil
77 N3ff6c34fab30496d8505e8221c53b059 schema:familyName Henzinger
78 schema:givenName Monika
79 rdf:type schema:Person
80 N474d643154e2492fb0cb45282b21b22b rdf:first sg:person.011757371347.43
81 rdf:rest N835df16aaa9b4e0baa384de54756d26c
82 N4b687b588da1434abee8c7b35ad08b64 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N540f8ef7140e4b6cadc4f93d99e1e782 schema:name dimensions_id
85 schema:value pub.1011131440
86 rdf:type schema:PropertyValue
87 N6c9cc44e85df425c89345e378ffe9862 rdf:first N3ff6c34fab30496d8505e8221c53b059
88 rdf:rest N01b5ec9560f1487ca8b4102e1d11c4bb
89 N6e6e47acbf7b4e68b6b0ba235970fa20 rdf:first Nb239369011a04c139bbeb81e609cb0ae
90 rdf:rest N6c9cc44e85df425c89345e378ffe9862
91 N724e67dfed4245cbb85704165bbc71de rdf:first sg:person.011513671015.17
92 rdf:rest N474d643154e2492fb0cb45282b21b22b
93 N79d01b08bbfa403cbca4ba21d3dfc677 schema:familyName Sgall
94 schema:givenName Jiří
95 rdf:type schema:Person
96 N835df16aaa9b4e0baa384de54756d26c rdf:first sg:person.010731762606.52
97 rdf:rest rdf:nil
98 Nb239369011a04c139bbeb81e609cb0ae schema:familyName Aceto
99 schema:givenName Luca
100 rdf:type schema:Person
101 Nc1b7d400121845f3a16d5ed79ba3aff3 schema:isbn 978-3-642-22011-1
102 978-3-642-22012-8
103 schema:name Automata, Languages and Programming
104 rdf:type schema:Book
105 Ncf8c78371836410ebc0c9b23c815e56e schema:name doi
106 schema:value 10.1007/978-3-642-22012-8_38
107 rdf:type schema:PropertyValue
108 Nf41b5bd1d23947c9b8d05f2cf7b9b642 schema:name Springer Nature
109 rdf:type schema:Organisation
110 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
111 schema:name Information and Computing Sciences
112 rdf:type schema:DefinedTerm
113 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
114 schema:name Artificial Intelligence and Image Processing
115 rdf:type schema:DefinedTerm
116 sg:person.010731762606.52 schema:affiliation grid-institutes:grid.1001.0
117 schema:familyName Schweitzer
118 schema:givenName Pascal
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010731762606.52
120 rdf:type schema:Person
121 sg:person.011513671015.17 schema:affiliation grid-institutes:grid.419528.3
122 schema:familyName Megow
123 schema:givenName Nicole
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011513671015.17
125 rdf:type schema:Person
126 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
127 schema:familyName Mehlhorn
128 schema:givenName Kurt
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
130 rdf:type schema:Person
131 grid-institutes:grid.1001.0 schema:alternateName The Australian National University, Canberra, Australia
132 schema:name The Australian National University, Canberra, Australia
133 rdf:type schema:Organization
134 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Saarbrücken, Germany
135 schema:name Max-Planck-Institut für Informatik, Saarbrücken, Germany
136 rdf:type schema:Organization
 




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


...