We study the following graph exploration problems.
First we consider the problem of exploration of trees, some of whose
edges are faulty. An agent, 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. We interested in a
fastest exploration, i.e. minimizing the number of edge traversals.
Another scenario is a graph with a black hole. A black hole is a
highly harmful stationary process residing in a node of a network and
destroying all mobile agents visiting the node, without leaving any
trace. We consider the task of locating a black hole in a (partially)
synchronous network, assuming an upper bound on the time of any edge
traversal by an agent. The minimum number of agents capable to
identify a black hole is two. For a given graph and given starting
node we are interested in the fastest possible black hole search by
two agents.
We study the time complexity of the above problems in several graph topologies.