Fixed Parameter Tractable Algorithm for Firefighting Problem
Fixed Parameter Tractable Algorithm for Firefighting Problem
复制标题
消防问题的定参数易处理算法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Ming Lam Leung
中科院分区：
文献类型：
--
作者：
Ming Lam Leung
消防员问题的定义如下。最初，大火在图G上的顶点爆发。在每个步骤中，消防员选择保护一个尚未燃烧的顶点。之后，大火蔓延到其未受保护的相邻顶点。问题的目的是选择一系列顶点来保护，以便从火中节省最大数量的顶点。
在本文中，我们将在消防员问题中引入一个参数k，并使用CAI，Chan和Chan的随机分离技术给出多种FPT算法。如果将顶点总数刻录为参数，我们将证明消防员问题在一般图上是FPT。如果我们对受保护的顶点的数量进行参数化，我们会在度界图和独立图形上发现消防员问题的几种FPT算法。此外，我们还研究了加权图和有价值的图表上的消防员问题，以及与学位结合图的多个消防源的问题。
The firefighter problem is defined as below. A fire initially breaks out at a vertex r on a graph G. In each step, a firefighter chooses to protect one vertex, which is not yet burnt. And the fire spreads out to its unprotected neighboring vertices afterwards. The objective of the problem is to choose a sequence of vertices to protect, in order to save maximum number of vertices from the fire.
In this paper, we will introduce a parameter k into the firefighter problem and give several FPT algorithms using a random separation technique of Cai, Chan and Chan. We will prove firefighter problem is FPT on general graph if we take total number of vertices burnt to be a parameter. If we parameterize the number of protected vertices, we discover several FPT algorithms of the firefighter problem on degree bounded graph and unicyclic graph. Furthermore, we also study the firefighter problem on weighted and valued graph, and the problem with multiple fire sources on degree-bounded graph.