Best effort decontamination of networks

Abstract

In this thesis we consider the problem to find the optimal strategy to decontaminate the maximum possible number of nodes in a contaminated network with a fixed number of agents. We are given a team of mobile agents located on a node in a contaminated network and the number of agents is not enough to decontaminate the whole network to reach a state in which all nodes are simultaneously clean. We want to find what the maximum number of decontaminated nodes is and how to decontaminate them. In this thesis we consider meshes (regular, octagonal, and hexagonal) and trees and give optimal strategies for those topologies. We also analyze the performance of our strategies according to the number of decontaminated nodes, number of agents' movement and time.