Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Scienze dell'Informazione - DSI
via Salaria 113, III piano
Aula Seminari

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 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, is called the overhead of algorithm for this class of graphs. We consider three scenarios, providing the robot with varying amount of information. The robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting node (an anchored map). For all of the above scenarios, we construct natural exploration algorithms that have smallest, or - in one ase - close to smallest, overhead. An important contribution of this work is establishing lower bounds that prove optimality of these exploration algorithms.

This is joint work with A. Dessmark.