Graph Searching and Related Problems

图搜索及相关问题

• 批准号: RGPIN-2018-06800
• 负责人: Yang, Boting
• 金额: $ 1.68万
• 依托单位: University of Regina
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=669149
• 关键词: Graph; Searching; Related; Problems

Graph Searching is a very active topic in graph theory, which is related to many graph parameters. In a typical graph searching problem, searchers (or cops) want to capture one or more moving entities (or robbers) on a graph. Many real-world problems can be modeled by an appropriate graph searching problem. Some examples include: police officers searching for fugitives, a search-and-rescue team searching for a missing person, a military troop clearing an area of enemies, robots searching for explosive devices in a building, or computer technicians searching for a virus on a computer network. We are especially interested in investigating computational issues of search strategies that are commonly used by people. ******Cops and Robbers is one of the most studied models for graph searching problems in the literature. It is a vertex-pursuit game played on graphs. In the Cops and Robbers game, a set of cops and a robber occupy the vertices of the graph and move alternately along the graph's edges with perfect information about each other's positions. The cops win if a cop eventually occupies the same vertex as the robber; the robber wins if he can indefinitely evade capture. ******Graphs provide natural models for domains such as roadways and networks. Graph searching is an especially useful way of solving problems in such domains because many relevant results from graph theory can be employed when considering the search number or cop number. In this proposal, we consider graph searching and related problems. Our proposed research focuses on the game of Cops and Robbers and its variants. We will investigate long-standing open problems such as Meyniel's conjecture and Schroeder's conjecture, which provide bounds for the cop number. We will also consider the computation of search strategies in the visible node search problem and variants of the Cops and Robbers game, which include the one-cop-moves game (also called Lazy Cops and Robbers) and the zero-visibility Cops and Robbers game. We will design algorithms and approximation algorithms for computing search strategies that are guaranteed to capture the robber. Many interesting questions arise with relation to this problem. For example, given a graph, what is the minimum number of searchers or cops required to catch the robber? And what is the minimum number of steps to search the graph? These questions are particularly important for applications where the number of searchers is limited. The proposed project addresses these questions using state-of-the-art tools from the areas of graph theory and algorithm design. Our research will provide new algorithms and eventually software that will assist in various search applications.

图搜索是图论中一个非常活跃的课题，它涉及到许多图的参数。在一个典型的图搜索问题中，搜索者（或警察）想要捕获图上的一个或多个移动实体（或强盗）。许多现实世界的问题可以通过适当的图搜索问题来建模。一些例子包括：搜索逃犯的警察、搜索失踪人员的搜索和救援队、清除敌人区域的军队、在建筑物中搜索爆炸装置的机器人或在计算机网络上搜索病毒的计算机技术人员。我们特别感兴趣的是调查计算问题的搜索策略，通常使用的人。**Cops and Robbers是文献中研究最多的图搜索问题模型之一。这是一个在图上进行的顶点追踪游戏。在“警察和强盗”博弈中，一组警察和一个强盗占据图的顶点，并沿着图的边交替移动，同时掌握彼此位置的完美信息。 如果警察最终占据了与劫匪相同的顶点，那么警察就赢了;如果劫匪能够无限期地逃避追捕，那么他就赢了。** 图为道路和网络等领域提供了自然模型。图搜索是一种特别有用的方法来解决这些领域中的问题，因为当考虑搜索数或copnumber时，可以采用图论中的许多相关结果。在这个建议中，我们考虑图搜索和相关的问题。我们建议的研究重点是警察和强盗的游戏及其变体。我们将研究长期存在的开放问题，如Meyniel猜想和Schroeder猜想，这些问题为cop数提供了界限。我们还将考虑可见节点搜索问题中搜索策略的计算以及Cops and Robbers博弈的变体，其中包括one-cop-moves博弈（也称为Lazy Cops and Robbers）和零可见性Cops and Robbers博弈。我们将设计算法和近似算法来计算搜索策略，以保证捕获强盗。许多有趣的问题与这个问题有关。例如，给定一个图，需要多少搜索者或警察才能抓住抢劫犯？搜索图的最少步骤是多少？这些问题对于搜索者数量有限的应用程序尤其重要。拟议的项目解决这些问题，使用最先进的工具，从图论和算法设计领域。我们的研究将提供新的算法，并最终软件，将有助于各种搜索应用程序。