论文标题
飞机上的点燃烧数字
Burning Number for the Points in the Plane
论文作者
论文摘要
图$ g $上的燃烧过程始于一个燃烧的顶点，在随后的每个步骤中，燃烧了当前燃烧的顶点的邻居，以及其他一个未燃烧的顶点。 $ g $的燃烧数量是燃烧图形所有顶点所需的最小步骤。在本文中，我们研究了在几何环境中计算燃烧数量的问题。输入是欧几里得飞机中的一组点$ p $。燃烧过程始于单个燃烧点，在随后的每个步骤中，燃烧的所有点与当前燃烧点的一个单位距离内，另一个未燃烧点。 $ p $的燃烧数量是燃烧$ p $的所有点所需的最小步骤。我们称此变体\ emph {point burning}。我们考虑了另一个称为\ emph {where burning}的变体，在那里我们被允许燃烧平面的任何点。我们证明了该点燃烧，任何燃烧问题都均为NP complete，但是每$ \ varepsilon> 0 $ able $（2+ \ varepsilon）$。此外，如果我们对可以使用的燃烧来源的数量进行限制，那么燃烧问题就会变成np-hard，以在$ \ frac {2} {2} {\ sqrt {3}}}}}} - \ varepsilon $之内。
The burning process on a graph $G$ starts with a single burnt vertex, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as one other unburnt vertex. The burning number of $G$ is the smallest number of steps required to burn all the vertices of the graph. In this paper, we examine the problem of computing the burning number in a geometric setting. The input is a set of points $P$ in the Euclidean plane. The burning process starts with a single burnt point, and at each subsequent step, burns all the points that are within a distance of one unit from the currently burnt points and one other unburnt point. The burning number of $P$ is the smallest number of steps required to burn all the points of $P$. We call this variant \emph{point burning}. We consider another variant called \emph{anywhere burning}, where we are allowed to burn any point of the plane. We show that point burning and anywhere burning problems are both NP-complete, but $(2+\varepsilon)$ approximable for every $\varepsilon>0$. Moreover, if we put a restriction on the number of burning sources that can be used, then the anywhere burning problem becomes NP-hard to approximate within a factor of $\frac{2}{\sqrt{3}}-\varepsilon$.
