Impact of topographic information on graph exploration efficiency

A robot has to explore an undirected connected graph by visiting all its no des and traversing all edges. It may either have a complete a priori knowle dge of the graph or only have an unoriented map of it, or, finally, lack an y knowledge of the graph. We study the impact of this varying amount of kno wledge on exploration performance. It is shown that the best exploration al gorithm lacking any knowledge of the graph uses twice as many edge traversa ls in the worst case as does the best algorithm which has an unoriented map of the graph. On the other hand, the latter uses twice as many edge traver sals in the worst case as does the best algorithm having a complete knowled ge of the graph. Similar results for the restricted case of exploration alg orithms working only for trees are also established. (C) 2000 John Wiley & Sons, Inc.