---
res:
bibo_abstract:
- We consider exploration problems where a robot has to construct a complete map
of an unknown environment. We assume that the environment is modeled by a directed,
strongly connected graph. The robot's task is to visit all nodes and edges of
the graph using the minimum number R of edge traversals. Deng and Papadimitriou
[Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990,
pp. 356-361] showed an upper bound for R ofd O(d)m and Koutsoupias (reported by
Deng and Papadimitriou) gave a lower bound of Ω≠(d2m), where m is the number of
edges in the graph and d is the minimum number of edges that have to be added
to make the graph Eulerian. We give the 1rst subexponential algorithm for this
exploration problem, which achieves an upper bound of dO(logd)m. We also show
a matching lower bound of d≠(logd)m for our algorithm. Additionally, we give lower
bounds of 2≠(d)m, respectively, d≠(logd)m for various other natural exploration
algorithms.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Susanne
foaf_name: Albers, Susanne
foaf_surname: Albers
- foaf_Person:
foaf_givenName: Monika H
foaf_name: Henzinger, Monika H
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
orcid: 0000-0002-5008-6530
bibo_doi: 10.1137/s009753979732428x
bibo_issue: '4'
bibo_volume: 29
dct_date: 2000^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0097-5397
- http://id.crossref.org/issn/1095-7111
dct_language: eng
dct_publisher: Society for Industrial and Applied Mathematics@
dct_subject:
- directed graph
- exploration algorithm
dct_title: Exploring unknown environments@
...