---
_id: '11694'
abstract:
- lang: eng
  text: 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.
acknowledgement: We thank Prabhakar Raghavan for bringing to our attention the literature
  on the s-t connectivity  problem. We also thank  an anonymous referee for many helpful
  comments which improved the presentation of the paper.
article_processing_charge: No
article_type: original
author:
- first_name: Susanne
  full_name: Albers, Susanne
  last_name: Albers
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: Albers S, Henzinger MH. Exploring unknown environments. <i>SIAM Journal on
    Computing</i>. 2000;29(4):1164-1188. doi:<a href="https://doi.org/10.1137/s009753979732428x">10.1137/s009753979732428x</a>
  apa: 'Albers, S., &#38; Henzinger, M. H. (2000). Exploring unknown environments.
    <i>SIAM Journal on Computing</i>. El Paso, TX, United States: Society for Industrial
    and Applied Mathematics. <a href="https://doi.org/10.1137/s009753979732428x">https://doi.org/10.1137/s009753979732428x</a>'
  chicago: Albers, Susanne, and Monika H Henzinger. “Exploring Unknown Environments.”
    <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics,
    2000. <a href="https://doi.org/10.1137/s009753979732428x">https://doi.org/10.1137/s009753979732428x</a>.
  ieee: S. Albers and M. H. Henzinger, “Exploring unknown environments,” <i>SIAM Journal
    on Computing</i>, vol. 29, no. 4. Society for Industrial and Applied Mathematics,
    pp. 1164–1188, 2000.
  ista: Albers S, Henzinger MH. 2000. Exploring unknown environments. SIAM Journal
    on Computing. 29(4), 1164–1188.
  mla: Albers, Susanne, and Monika H. Henzinger. “Exploring Unknown Environments.”
    <i>SIAM Journal on Computing</i>, vol. 29, no. 4, Society for Industrial and Applied
    Mathematics, 2000, pp. 1164–88, doi:<a href="https://doi.org/10.1137/s009753979732428x">10.1137/s009753979732428x</a>.
  short: S. Albers, M.H. Henzinger, SIAM Journal on Computing 29 (2000) 1164–1188.
conference:
  end_date: 1997-05-06
  location: El Paso, TX, United States
  name: 'STOC97: 29th Annual Symposium on Theory of Computing'
  start_date: 1997-05-04
date_created: 2022-07-29T09:04:36Z
date_published: 2000-07-01T00:00:00Z
date_updated: 2023-02-17T14:41:36Z
day: '01'
doi: 10.1137/s009753979732428x
extern: '1'
intvolume: '        29'
issue: '4'
keyword:
- directed graph
- exploration algorithm
language:
- iso: eng
month: '07'
oa_version: None
page: 1164-1188
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Exploring unknown environments
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 29
year: '2000'
...