Grant: Discovery Grants Program - Individual

A graph is an abstract idea used to model relationships between important objects, people or ideas. Thus, maps, computer networks, and even family trees can be represented as graphs. This research is interested in moving through graphs - like getting directions on how to drive between two different cities. Particularly, this research deals with searching and domination problems, which 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 guard against attacks by malicious "intruders", and subsequently how to capture these intruders if they do attack. 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, while graph domination can be thought of as how to distribute guards to minimize damage if an attack occurs. In one popular formulation, 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 deals with minimizing the response time after an attack, and then how to minimize the cost of the response when the intruder's position is uncertain. 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 graph domination problems. It will also provide training opportunities for graduate and undergraduate students.