Lisa Song
In a networked environment, intruders are defined as possible harmful mobile age nts penetrated into the environment. If intruders are detected in a network, we must clean that contaminated network to restore its normal operations. In the i ntruder capture problem, intruders move along the network links and capturers (m obile agents) also move along the network to capture the intruders at network no des or links. However, the intruders could be arbitrarily fast and aware of the positions of all the capturers, hence the intruders may escape from the capturer s. The efficiency of the intruder capture algorithm is the size of the agent tea m to capture the intruders.
The intruder capture problem is an instance of the continuous graph searching pr oblems, and many graph searching algorithms can be related to it and some have b een developed to capture intruders by using mobile agents, such as capturing int ruders in a tree. In this discussion, we will study the intruder capturing probl em in a tree topology network. For any tree T, we have a linear-time algorithm that computes the minimum number of agents to capture the intruder.