Time and motion in graphs

图表中的时间和运动

• 批准号: RGPIN-2015-03946
• 负责人: Dyer, Danny
• 金额: $ 0.8万
• 依托单位: Memorial University of Newfoundland
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=612674
• 关键词: Time; motion; graphs

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.

边缘搜索是一种图搜索模型，在这种模型中，一组缓慢的、可见的搜索者在图G的一个顶点到另一个顶点移动，以捕获一个快速的、不可见的入侵者，这个入侵者可能在顶点和边缘上都停了下来。捕获入侵者所需的最小搜索者数量被称为边缘搜索数g。搜索问题可以应用于搜索和救援，视频游戏人工智能，甚至清洁核电站供水管道。