Efficient Self-Stabilizing Graph Searching in Tree Networks

Download Now Date Added: Sep 2010
Format: PDF

Networks of computing devices enable fast communication, pervasive sharing of information, and effective distributed computations that might otherwise be infeasible. Unfortunately, this comes at the cost of fast spreading viruses and malicious software agents. The fact that modern networks are constantly changing exacerbates the problem. Thus, it is important to regularly search a network in order to eliminate malicious software. This setting has been formalized as various graph search problems where one asks for a strategy that will clear a graph of any unwanted "Intruders" typically using as few operations as possible.