Optimal graph exploration without good maps
(2002) Algorithms - ESA 2002. 10th Annual European Symposium. Proceedings 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:
https://lup.lub.lu.se/record/611793
- author
- Dessmark, Anders LU and Pelc, A.
- organization
- publishing date
- 2002
- 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
- host publication
- 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
- conference location
- Rome, Italy
- conference dates
- 2002-09-17 - 2002-09-21
- 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
- 2016-04-04 11:06:11
- date last changed
- 2022-03-31 17:59:18
@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}},
keywords = {{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}},
url = {{http://www.springerlink.com/content/f1rhfyfxj5ekttrg/}},
volume = {{2461}},
year = {{2002}},
}