Spreading and Containment in Graphs

图中的传播和遏制

• 批准号: 269574128
• 负责人: Professor Dr. Dieter Rautenbach
• 金额: --
• 依托单位: Institut für Optimierung und Operations Research
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2016-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/269574128?language=en
• 关键词: Spreading; Containment; Graphs

Expansion processes occur in essentially every real world network. Examples are the spreading of a virus within a computer network or a society, or the propagation of a rumor within a social network. If the spreading is undesired as in the case of a virus, there are natural containment strategies that rely on the protection of individual nodes of the network. Graph theory offers a suitable setting to mathematically model and investigate such spreading and containment processes. In this project we want to study the so-called -) irreversible dynamic monopolies as a simple graph theoretical spreading model and -) the firefighter game as a simple graph theoretical containment model. Our goals are structural and algorithmic results concerning these two fundamental notions and their variants.

扩张过程基本上发生在每个现实世界的网络中。例如，病毒在计算机网络或社会中的传播，或谣言在社交网络中的传播。如果传播是不受欢迎的，就像病毒的情况一样，有自然的遏制策略，依赖于对网络个别节点的保护。图论提供了一个合适的环境来对这种传播和遏制过程进行数学建模和研究。在这个项目中，我们想要将所谓的不可逆动态垄断作为一个简单的图论扩散模型来研究，以及-)将消防员博弈作为一个简单的图论包容模型来研究。我们的目标是关于这两个基本概念及其变体的结构和算法结果。

项目成果

Some bounds on the zero forcing number of a graph

• DOI: 10.1016/j.dam.2017.11.015
• 发表时间: 2016-08
• 期刊: Discret. Appl. Math.
• 作者: Michael Gentner;D. Rautenbach

Extremal values and bounds for the zero forcing number

• DOI: 10.1016/j.dam.2016.06.004
• 发表时间: 2016-12
• 期刊: Discret. Appl. Math.
• 作者: Michael Gentner;L. Penso;D. Rautenbach;U. Souza

Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees

周长至少为五的连通图中的度比例阈值和树的动态垄断

• DOI: 10.1016/j.tcs.2016.12.028
• 发表时间: 2017
• 期刊: Theor. Comput. Sci.
• 作者: M. Gentner;D. Rautenbach
• 通讯作者: D. Rautenbach

Generalized threshold processes on graphs

图上的广义阈值过程

• DOI: 10.1016/j.tcs.2017.05.010
• 发表时间: 2017
• 期刊: Theor. Comput. Sci.
• 作者: C.V.G.C. Lima;D. Rautenbach;U.S. Souza;J.L. Szwarcfiter
• 通讯作者: J.L. Szwarcfiter