Optimal graph exploration without good maps

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Abstract

A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm A is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class

Details

Authors
  • Anders Dessmark
  • A. Pelc
Research areas and keywords

Subject classification (UKÄ)

  • Computer Science

Keywords

  • natural exploration algorithms, undirected connected graph, optimal graph exploration, lower bounds, edge traversals, robot
Original languageEnglish
Title of host publicationAlgorithms - ESA 2002. 10th Annual European Symposium. Proceedings (Lecture Notes in Computer Science Vol.2461)
PublisherSpringer
Pages374-386
Volume2461
ISBN (Print)3-540-44180-8
Publication statusPublished - 2002
Publication categoryResearch
Peer-reviewedYes
EventAlgorithms - ESA 2002. 10th Annual European Symposium. Proceedings - Rome, Italy
Duration: 2002 Sep 172002 Sep 21

Publication series

Name
Volume2461

Conference

ConferenceAlgorithms - ESA 2002. 10th Annual European Symposium. Proceedings
Country/TerritoryItaly
CityRome
Period2002/09/172002/09/21