Grant: Discovery Grants Program - Individual

In this proposal, we consider some graph theoretic problems. The motivation for some of the proposed work, primarily searching, comes from theoretical computer science where the problems being developed usually have a dynamic nature. The research program described here has several themes. For instance, we will often be interested in studying the structural properties of the graphs under consideration. One application of the proposed research is network security. Cyber attacks are becoming increasingly problematic as faster and more destructive intruders, such as viruses and worms, are developed. Many of our current defenses, including antivirus software and firewalls, focus on local protection. Security can be greatly enhanced through the use of algorithms designed to first locate and then to quarantine the propagation of the intruder. The theory underlying such algorithms comes from an area of mathematics known as ""searching networks"". The searching networks problem was originally proposed by Tory Parsons in 1978 in response to inquires made by the spelunking community. Searching can be thought of as a pursuit game played on a graph, with the opposing sides being a finite set of searchers and the intruder. There are a variety of models. One such model, known as the Cops and Robber model, was traditionally played with perfect information, meaning that both sides were aware of the movements of their opponent(s). My proposal includes variations in which the searchers (cops) have only partial information. In addition to network security, applications include criminal apprehension, building security, and the tracking of users in cellular networks.