The firebreak problem
The firebreak problem
复制标题
DOI：
10.1002/net.21975
复制
发表时间：
2020-08-21
期刊：
影响因子：
2.1
通讯作者：
Ryan, Brady
中科院分区：
文献类型：
--
作者：
Barnetson, Kathleen D.;Burgess, Andrea C.;Ryan, Brady
假设我们有一个用图G表示的网络。潜在的火（或其他类型的传染）可能在G的某个顶点爆发。我们能够通过在G的k个其他顶点建立防火线来应对这种爆发，这样火就不能穿过这些设防的顶点。现在出现的问题是，假设火将蔓延到所有没有完全在防火线k个顶点后面的顶点，那么哪个k个顶点将导致最大数量的顶点被从火中拯救出来。这就是火灾决策问题的本质，也是本文的重点。我们建立，这个问题是棘手的分裂图类以及二分图类，但可以在线性时间内解决时，限制到图具有恒定有界树宽，或在多项式时间内限制到相交图。我们还考虑了一些密切相关的问题。
Suppose we have a network that is represented by a graphG. Potentially a fire (or other type of contagion) might erupt at some vertex ofG. We are able to respond to this outbreak by establishing a firebreak atkother vertices ofG, so that the fire cannot pass through these fortified vertices. The question that now arises is whichkvertices will result in the greatest number of vertices being saved from the fire, assuming that the fire will spread to every vertex that is not fully behind thekvertices of the firebreak. This is the essence of theFirebreakdecision problem, which is the focus of this paper. We establish that the problem is intractable on the class of split graphs as well as on the class of bipartite graphs, but can be solved in linear time when restricted to graphs having constant-bounded treewidth, or in polynomial time when restricted to intersection graphs. We also consider some closely related problems.