Optimal constrained graph exploration

Christian A. Duncan, Stephen G. Kobourov, V. S. Anil Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Scopus citations

Abstract

We address the problem of exploring an unknown graph G = (V, E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. In the tethered robot case, if the tether (rope) has length /, then the robot must remain within distance / from the start node s. In the second variation, a fuel tank of limited capacity forces the robot to return to s after traversing C edges. The efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot which explores the graph in &Ogr;(|E|) edge traversais. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a &Ogr;(|E|) algorithm. This improves on the previous best known bound of &Ogr;(|E| + \V|2log 2|V|) in [4]. Since the lower bound for the graph exploration problems is |E|, our algorithm is optimal, thus answering the open problem of Awerbuch, Betke, Rivest, and Singh [3].

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery (ACM)
Pages807-814
Number of pages8
ISBN (Print)0898714907
StatePublished - 2001
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2001 Operating Section Proceedings, American Gas Association
Country/TerritoryUnited States
CityDallas, TX
Period4/30/015/1/01

Keywords

  • Algorithms
  • Design
  • Performance
  • Theory
  • Verification

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Optimal constrained graph exploration'. Together they form a unique fingerprint.

Cite this