Efficient Exploration of Faulty Trees |
| |
Authors: | Euripides Markou Andrzej Pelc |
| |
Affiliation: | (1) Departement d'informatique, Universite du Quebec en Outaouais, Gatineau, Quebec, J8X 3X7, Canada |
| |
Abstract: | We consider the problem of the exploration of trees, some of whose edges are faulty. A robot, situated in a starting node
and unaware of the location of faults, has to explore the connected fault-free component of this node by visiting all its
nodes. The cost of the exploration is the number of edge traversals. For a given tree and given starting node, the overhead
of an exploration algorithm is the worst-case ratio (taken over all fault configurations) of its cost to the cost of an optimal
algorithm which knows where faults are situated. An algorithm, for a given tree and given starting node, is called perfectly
competitive if its overhead is the smallest among all exploration algorithms not knowing the location of faults.
We design a perfectly competitive exploration algorithm for any line, and an exploration algorithm for any tree, whose overhead
is at most 9/8 larger than that
of a perfectly competitive algorithm. Both our algorithms are fairly natural and the total time of local computations used
during exploration is linear in the size of the explored tree. Our main contribution is the analysis of the performance of
these algorithms, showing that natural exploration strategies perform well in faulty trees. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|