Graph Protection and Domination

图保护和统治

• 批准号: RGPIN-2020-03930
• 负责人: Mynhardt, Christina
• 金额: $ 1.75万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=739570
• 关键词: Graph; Protection; Domination

The long term goal of this program is to fuel advances in the theory of graph protection. A graph is a network of nodes linked in a prescribed way. These nodes could be islands, for example, with two nodes being linked when there is a direct ferry service between them. The term protection arises from a military strategy used by Emperor Constantine in ca. 300 AD to protect the Roman Empire. Graph protection involves the placement of resources at strategically located nodes. If it is impossible, for example, that every island has its own school, can we build schools and design ferry routes so that each island without a school is only a single ferry ride away from one? What are the costs involved? My research focuses on the theory of graph protection. Viewing the resources at nodes as stationary surveillance equipment, they can safeguard a graph against intruders when each location is visible to (say) a camera or motion sensor. Viewed as broadcasting units, they can spread information through the graph. In terms of security, one may instead view the resources as mobile guards, a term that may be interpreted as military personnel, emergency services, etc. Imagine an emergency situation where a node is attacked by an intruder. If a guard is located at the node, they can defend it. Otherwise, a guard from an adjacent node must move across a link to the attacked node. After each move, each node must either have a guard or be linked to a node with a guard. This enables guards to repel repeated attacks without returning to their previous positions. To mount a successful defence, there is a conflict between cost and efficiency, both depending on the number of guards and their mobility. The challenge is to balance these opposing factors. I aim to use innovative ideas to further develop models for optimal protection strategies. My research involves aspects such as determining the cost, efficiency and quality of the defence according to different models, and optimising the number of guards required for a successful defence. Other important considerations are studying the stability and vulnerability of particular networks, and analysing networks that permit efficient strategies. I aim to make breakthroughs in solving major open problems in these areas, and to publish the results in peer reviewed journals. Such results will make important contributions to building a comprehensive theory of graph protection by filling existing gaps and opening new avenues of investigation. This theory can inform facilities placement policies and assess influence in social networks. Transitioning between different optimal solutions provides information on both the number of such solutions and their relationship to one another. The training and mentoring of a diverse team of research students, which forms an integral component of my research program, will facilitate capacity building to ensure that Canada remains competitive in STEM fields in the future.

该计划的长期目标是推动图形保护理论的发展。图是以规定方式连接的节点的网络。这些节点可以是岛，例如，当两个节点之间有直接渡轮服务时，两个节点被连接。“保护”一词源于君士坦丁大帝在公元前1000年使用的一种军事战略。公元300年保护罗马帝国。图保护涉及将资源放置在战略位置的节点上。例如，如果不可能每个岛屿都有自己的学校，我们是否可以建立学校和设计渡轮航线，使每个没有学校的岛屿与一个学校只有一次渡轮之遥？所涉及的费用是多少？本文的研究主要集中在图的保护理论上。将节点上的资源视为固定的监视设备，当每个位置对（例如）摄像头或运动传感器可见时，它们可以保护图形免受入侵者的攻击。它们被视为广播单元，可以通过图形传播信息。在安全性方面，人们可以将资源视为移动的警卫，这一术语可以解释为军事人员、紧急服务等。想象一下节点受到入侵者攻击的紧急情况。如果一个守卫位于该节点上，他们就可以保卫它，否则，来自相邻节点的守卫必须穿过一条链路到达被攻击的节点。在每次移动之后，每个节点必须有一个守卫或链接到一个有守卫的节点。这使警卫能够击退反复的攻击，而不必返回先前的位置。为了成功地进行辩护，成本和效率之间存在冲突，这两者都取决于警卫的数量和他们的机动性。我们面临的挑战是如何平衡这些对立的因素。我的目标是使用创新的想法，进一步开发最佳保护策略的模型。我的研究涉及根据不同模型确定防守的成本、效率和质量，以及优化成功防守所需的后卫数量等方面。其他重要的考虑因素是研究特定网络的稳定性和脆弱性，并分析允许有效战略的网络。我的目标是在解决这些领域的主要开放问题方面取得突破，并将结果发表在同行评审的期刊上。这些结果将填补现有的空白，开辟新的研究途径，为建立一个全面的图保护理论做出重要贡献。这一理论可以为设施布局政策提供信息，并评估社交网络中的影响。在不同的最佳解决方案之间的转换提供了关于这些解决方案的数量以及它们彼此之间的关系的信息。培训和指导一个多元化的研究生团队，这是我的研究计划的一个组成部分，将促进能力建设，以确保加拿大在未来的STEM领域保持竞争力。