Exploration of graphs under different scenarios

Euripides Markou
National and Kapodistrian University, Athenes


Abstract:

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.

Retour au séminaire