Grant: Discovery Grants Program - Individual

Edge searching is a graph searching model in which a collection of slow, visible searchers move from vertex to vertex in a graph G to capture a fast, invisible intruder that may stop on both vertices and edges. The minimum number of searchers needed to capture the intruder is known as the edge search number of G. Searching problems have applications to search and rescue, video game artificial intelligence, and even to cleaning nuclear plant water supply pipes. This research deals with using software agents to capture a malicious mobile ""intruder"" such as a computer virus. Discrete pursuit-evasion (also called graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. In this particular formulation of the pursuit-evasion problem, the environment is a computer network and it is modeled as a graph. Classically, the problem has been to determine the minimum number of agents needed to capture the intruder. This research program is to consider instead how to move agents in such ways as to quickly capture the intruder. Alternatively, we might consider how to move the agents in such a way as to minimize the number of man-hours required, instead of minimizing the number of agents or time required. These problems are difficult to solve, even with computers, and consequently we need theoretical research, like that involved in this program of research, to ""cut corners"" and make this more practical. Because of the applications of this research to network security problems, the proposed research is likely to have impact in the design and construction of computer networks to minimize damage caused by malicious agents, and will contribute to the advancement of mathematical research in graph searching and related problems. It will also provide training opportunities for graduate and undergraduate students.