Graph protection and domination

图保护和统治

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

Graph protection and domination involves the placement of guards (or surveillance/broadcasting equipment, or emergency services, etc.) at strategic positions in a network. Positions in a network can be modelled by vertices of a graph, two vertices being adjacent if the corresponding positions in the network are, in some appropriate sense, reachable from each other. The guards deal with problems (called attacks) at vertices adjacent to their positions. Depending on the protection model the guards either remain stationary ("guards" here could mean "broadcast towers" or "smart servers on power lines") or move across edges of the graph to defend other vertices against an attack (or an ambulance moves to deal with an emergency); every vertex of the graph must have access to a guard (etc.) in this way. There is a conflict between cost, which is proportional to the number of guards, and efficiency, and it is a challenge to balance the opposing forces.

图形保护和控制涉及警卫（或监视/广播设备，或紧急服务等）的放置。在网络中的战略位置。网络中的位置可以用图的顶点来建模，如果网络中的相应位置在某种适当的意义上彼此可达，则两个顶点相邻。守卫处理与其位置相邻的顶点上的问题（称为攻击）。根据保护模型，守卫要么保持静止（这里的“守卫”可能意味着“广播塔”或“电力线上的智能服务器”），要么在图的边缘移动以保护其他顶点免受攻击（或救护车移动以处理紧急情况）;图的每个顶点都必须能够访问守卫（等等）。以这种方式。与警卫人数成正比的成本与效率之间存在冲突，平衡对立力量是一项挑战。