@inproceedings{136e4235627440e28d0cd760242547c8,

title = "Optimal graph exploration without good maps",

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",

keywords = "natural exploration algorithms, undirected connected graph, optimal graph exploration, lower bounds, edge traversals, robot",

author = "Anders Dessmark and A. Pelc",

year = "2002",

language = "English",

isbn = "3-540-44180-8",

volume = "2461",

publisher = "Springer",

pages = "374--386",

booktitle = "Algorithms - ESA 2002. 10th Annual European Symposium. Proceedings (Lecture Notes in Computer Science Vol.2461)",

address = "Germany",

note = "Algorithms - ESA 2002. 10th Annual European Symposium. Proceedings ; Conference date: 17-09-2002 Through 21-09-2002",

}