Advanced

Optimal graph exploration without good maps

Dessmark, Anders LU and Pelc, A. (2002) Algorithms - ESA 2002. 10th Annual European Symposium. Proceedings In Algorithms - ESA 2002. 10th Annual European Symposium. Proceedings (Lecture Notes in Computer Science Vol.2461) 2461. p.374-386
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
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
natural exploration algorithms, undirected connected graph, optimal graph exploration, lower bounds, edge traversals, robot
in
Algorithms - ESA 2002. 10th Annual European Symposium. Proceedings (Lecture Notes in Computer Science Vol.2461)
volume
2461
pages
374 - 386
publisher
Springer
conference name
Algorithms - ESA 2002. 10th Annual European Symposium. Proceedings
external identifiers
  • wos:000181470400031
  • scopus:84938095433
ISBN
3-540-44180-8
language
English
LU publication?
yes
id
136e4235-6274-40e2-8d0c-d760242547c8 (old id 611793)
alternative location
http://www.springerlink.com/content/f1rhfyfxj5ekttrg/
date added to LUP
2007-11-27 11:44:34
date last changed
2017-03-19 04:25:23
@inproceedings{136e4235-6274-40e2-8d0c-d760242547c8,
  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},
  author       = {Dessmark, Anders and Pelc, A.},
  booktitle    = {Algorithms - ESA 2002. 10th Annual European Symposium. Proceedings (Lecture Notes in Computer Science Vol.2461)},
  isbn         = {3-540-44180-8},
  keyword      = {natural exploration algorithms,undirected connected graph,optimal graph exploration,lower bounds,edge traversals,robot},
  language     = {eng},
  pages        = {374--386},
  publisher    = {Springer},
  title        = {Optimal graph exploration without good maps},
  volume       = {2461},
  year         = {2002},
}