Graph Protection and Domination

图保护和统治

基本信息

  • 批准号:
    RGPIN-2015-05442
  • 负责人:
  • 金额:
    $ 1.02万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2016
  • 资助国家:
    加拿大
  • 起止时间:
    2016-01-01 至 2017-12-31
  • 项目状态:
    已结题

项目摘要

Graph protection and domination involves the placement of guards (or surveillance or broadcast equipment, emergency services, military units, etc.) at strategic positions in a network. Interestingly, it has its historical roots in the time of the Roman Empire when Emperor Constantine devised a military strategy, called a defense in depth strategy. He deployed mobile field armies, units of forces powerful enough to secure the regions of the Roman Empire, to stop the intruding enemy, or to suppress insurrection. A field army was considered capable of deploying to an adjacent region only if it moved from a region where there was at least one other army to help launch it. Positions in a network are modelled by nodes of a graph, two nodes being joined by a line if the corresponding positions in the network are, in some appropriate sense, reachable from each other. The guards deal with problems, called attacks, in situ or at nodes adjacent to their positions. Depending on the model the guards either remain stationary or move across lines to repel an attack; every vertex of the graph must have access to a guard in this way. There is a conflict between cost and efficiency, both of which are proportional to the number of guards and the type of guard movements, and it is a challenge to balance the opposing forces. My research focuses on the abstract mathematical theory of these protection strategies. The theory involves aspects such as the smallest number of guards required for a successful defense, algorithms to find these numbers, the most efficient strategies, types of networks that allow efficient defense strategies, the stability and vulnerability of specific types of networks, and so on. It is often difficult to determine the minimum number of guards required for a particular kind of defense, therefore relating the protection parameters to other, more easily determined parameters, such as the number of nodes or lines, the diameter or radius of the graph, forms part of my work. This is important in order to place them within the context of well-studied concepts. Although the protection models described above arose from Constantine's military strategy, as models of modern military strategy they are oversimplified. Nevertheless, models are tools for reasoning about problems and provide ways to formalize concepts such as the effect of different defense strategies on the cost and quality of the defense, and of the destruction of links in a network on its efficiency. The ideas developed here are of interest as mathematical concepts and problems, and also have other potential applications, such as to voting strategies and the spread of diseases. My goal is to develop a comprehensive theory of these protection strategies, and to encourage other researchers to participate in the process. The training and mentoring of undergraduate and graduate research students forms an integral part of my proposal.
图形保护和控制涉及警卫(或监视或广播设备,紧急服务,军事单位等)的放置。在网络中的战略位置。有趣的是,它的历史根源是罗马帝国时期,当时君士坦丁大帝制定了一项军事战略,称为纵深防御战略。他部署了移动的野战军,这些部队的力量足以确保罗马帝国的地区安全,阻止入侵的敌人,或镇压叛乱。一支野战军只有从至少有一支其他军队帮助发动的地区转移出来,才被认为有能力部署到邻近地区。 网络中的位置由图的节点来建模,如果网络中的相应位置在某种适当的意义上彼此可达,则两个节点由一条线连接。警卫处理问题,称为攻击,在原地或在邻近他们的位置的节点。根据模型的不同,守卫要么保持静止,要么穿过线条来击退攻击;图的每个顶点都必须以这种方式访问守卫。成本和效率之间存在冲突,两者都与警卫的数量和警卫行动的类型成正比,平衡对立的力量是一个挑战。 我的研究重点是这些保护策略的抽象数学理论。该理论涉及到成功防御所需的最小防护数量、找到这些数量的算法、最有效的策略、允许有效防御策略的网络类型、特定类型网络的稳定性和脆弱性等方面。通常很难确定特定类型防御所需的最小防护数量,因此,将保护参数与其他更容易确定的参数(例如节点或线路的数量、图形的直径或半径)相关联构成了我的工作的一部分。这一点很重要,以便将它们置于经过充分研究的概念的范围内。 虽然上述保护模式源于君士坦丁的军事战略,但作为现代军事战略的模式,它们过于简单化。然而,模型是推理问题的工具,并提供了形式化概念的方法,例如不同防御策略对防御成本和质量的影响,以及网络中链接的破坏对其效率的影响。这里发展的思想是有趣的数学概念和问题,也有其他潜在的应用,如投票策略和疾病的传播。 我的目标是发展一个全面的理论,这些保护策略,并鼓励其他研究人员参与这一进程。对本科生和研究生的培训和指导是我的建议的一个组成部分。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Mynhardt, Christina其他文献

Mynhardt, Christina的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Mynhardt, Christina', 18)}}的其他基金

Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2020-03930
  • 财政年份:
    2022
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2020-03930
  • 财政年份:
    2021
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2020-03930
  • 财政年份:
    2020
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2015-05442
  • 财政年份:
    2019
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2015-05442
  • 财政年份:
    2018
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2015-05442
  • 财政年份:
    2017
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2015-05442
  • 财政年份:
    2015
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
domination concepts, edge and vertex orderings, and traceability of graphs
支配概念、边和顶点排序以及图的可追溯性
  • 批准号:
    249749-2005
  • 财政年份:
    2008
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
domination concepts, edge and vertex orderings, and traceability of graphs
支配概念、边和顶点排序以及图的可追溯性
  • 批准号:
    249749-2005
  • 财政年份:
    2007
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Domination and related topics in graph theory
图论中的支配及相关主题
  • 批准号:
    257842-2002
  • 财政年份:
    2006
  • 资助金额:
    $ 1.02万
  • 项目类别:
    University Faculty Award

相似海外基金

Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2020-03930
  • 财政年份:
    2022
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2020-03930
  • 财政年份:
    2021
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2020-03930
  • 财政年份:
    2020
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2015-05442
  • 财政年份:
    2019
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2015-05442
  • 财政年份:
    2018
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2015-05442
  • 财政年份:
    2017
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Protection and Domination
图保护和统治
  • 批准号:
    RGPIN-2015-05442
  • 财政年份:
    2015
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph protection and domination
图保护和统治
  • 批准号:
    249749-2010
  • 财政年份:
    2014
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph protection and domination
图保护和统治
  • 批准号:
    249749-2010
  • 财政年份:
    2013
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
Graph protection and domination
图保护和统治
  • 批准号:
    249749-2010
  • 财政年份:
    2012
  • 资助金额:
    $ 1.02万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了