论文标题
关于无限大开火位置问题
About the Infinite Windy Firebreak Location problem
论文作者
论文摘要
可以减轻野火的严重性，采取预防措施，例如建造壁炉是植被完全去除的土地。在本文中，我们将野火遏制的问题建模为无限图的优化问题，称为无限大开火位置。未知延伸的土地被建模为一个无限的图形，在该图中，顶点对应于火灾和边缘的区域，代表着从一个区域到另一个区域传播的火。在该领土上建造壁炉的建造被建模为在两个顶点之间的两个方向上移除边缘。可以安装的防火次数取决于预算限制。我们假设火灾在顶点的子集中点燃，并传播给邻居。目标是选择一个子集以卸下以包含火，并避免燃烧图的无限部分。我们证明，在有限的情况下，无限大风防火位置是综合的，我们解决了一些多项式案例。我们表明，对于某些类别的图形，无限的壁炉位置多项式将多项式减少到最小剪切，例如无限的网格图和多元网格。
The severity of wildfires can be mitigated adopting preventive measures like the construction of firebreaks that are strips of land from which the vegetation is completely removed. In this paper, we model the problem of wildfire containment as an optimization problem on infinite graphs called Infinite Windy Firebreak Location. A land of unknown extension is modeled as an infinite undirected graph in which the vertices correspond to areas subject to fire and edges represent the propagation of fire from an area to another. The construction of a firebreak on the territory is modeled as the removal of edges in both directions between two vertices. The number of firebreaks that can be installed depends on budget constraints. We assume that fire ignites in a subset of vertices and propagates to the neighbours. The goal is to select a subset of edges to remove in order to contain the fire and avoid burning an infinite part of the graph. We prove that Infinite Windy Firebreak Location is coNP-complete in restricted cases and we address some polynomial cases. We show that Infinite Windy Firebreak Location polynomially reduces to Min Cut for certain classes of graphs like infinite grid graphs and polyomino-grids.
