By author > Devismes Stéphane

Several works have investigated the minimal number of robots required to solve some collective task. Here, we consider the terminating (deterministic or probabilistic) exploration of a graph by a swarm of oblivious robots. We first propose a non-trivial lower bound for the case of ring graphs. We then extend our result to general graphs. Our general lower bound is tight since it gives the necessary and sufficient number of robots to explore several important classes of graphs: ring, grid, and torus.

Stéphane Devismes is associate professor at Université Grenoble Alpes (Grenoble, France) since 2008. He is a member of the Synchronous Team of the VERIMAG Laboratory. He received his Ph.D. in 2006 from the University of Picardie Jules Verne (Amiens, France). He has carried out broad research in theoretical issues of distributed fault-tolerant computing, especially relating to self-stabilization.