Time and motion in graphs

边搜索是一种图搜索模型，其中一组缓慢的可见搜索者在图G中从一个顶点移动到另一个顶点，以捕获可能在顶点和边上停止的快速的不可见入侵者。捕获入侵者所需的最小搜索者数称为G的边搜索数。搜索问题可以应用于搜索和救援，视频游戏人工智能，甚至清洁核电站供水管道。这项研究涉及使用软件代理捕获恶意的移动的“入侵者”，如计算机病毒。离散追踪-逃避（也称为图搜索）是数学和计算机科学中的一类问题，其中一组试图在环境中追踪另一组的成员。在这个特定的追逃问题的公式中，环境是一个计算机网络，它被建模为一个图。传统上，问题是确定捕获入侵者所需的最少代理数量。这项研究计划是考虑如何移动代理的方式，以快速捕获入侵者。或者，我们可以考虑如何移动代理，以减少所需的工时，而不是减少代理的数量或所需的时间。这些问题即使用计算机也很难解决，因此我们需要进行理论研究，就像本研究计划中所涉及的那样，以“抄近路”，使其更加实用。由于这项研究的应用，网络安全问题，拟议的研究可能会产生影响，在计算机网络的设计和建设，以尽量减少恶意代理造成的损害，并将有助于图搜索和相关问题的数学研究的进步。它还将为研究生和本科生提供培训机会。

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.**