Decontaminating Arbitrary Graphs by Mobile Agents: a Survey

Dorota Osula

Decontaminating Arbitrary Graphs by Mobile Agents: a Survey

Abstract

A team of mobile agents starting from homebases need to visit and clean all nodes of the network. The goal is to find a strategy, which would be optimal in the sense of the number of needed entities, the number of moves performed by them or the completion time of the strategy. Currently, the field of distributed graph searching by a team of mobile agents is rapidly expanding and many new approaches and models are being presented in order to better describe real life problems like decontaminating danger areas by a group of robots or cleaning networks from viruses. A centralized searching, when a topology of a graph is known in advance is well studied. This survey presents comprehensive results focusing mainly on an issue of the distributed monotone contiguous decontamination problem, including recent results for clearing graphs with and without a priori knowledge about its topology. We introduce a bibliography for various models, which differ on e.g., knowledge about a graph, properties of agents, time clock or size of the available memory.