论文标题
改进了在树上燃烧图的近似算法
Improved Approximation Algorithm for Graph Burning on Trees
论文作者
论文摘要
给定图形$ g =（v，e）$，\ gb {}的问题是从$ v $（称为燃烧序列）找到一系列节点，以燃烧整个图。这是一个离散的步骤过程，在每个步骤中，未燃烧的顶点被选为通过将其标记为燃烧节点来向其邻居传播火的代理。在下一个连续的步骤中，燃烧的节点将大火传播给邻居。目标是找到最小长度的燃烧顺序。 \ gb {}问题是通用图甚至二进制树的NP-螺栓。已知一些近似结果，包括通用图的$ 3 $ APPROXIMATION算法和树木的$ 2 $ - 近似算法。在本文中，我们提出了一种针对树木的近似算法，该算法最多$ \ lfloor 1.75b（t）\ rfloor + 1 $，其中$ b（t）$是最佳燃烧序列的长度，也称为树$ t $的燃烧数量。换句话说，我们达到了$（\ lfloor 1.75b（t）\ rfloor + 1）/b（t）$的近似系数。
Given a graph $G=(V,E)$, the problem of \gb{} is to find a sequence of nodes from $V$, called burning sequence, in order to burn the whole graph. This is a discrete-step process, in each step an unburned vertex is selected as an agent to spread fire to its neighbors by marking it as a burnt node. A node that is burnt spreads the fire to its neighbors at the next consecutive step. The goal is to find the burning sequence of minimum length. The \gb{} problem is NP-Hard for general graphs and even for binary trees. A few approximation results are known, including a $3$-approximation algorithm for general graphs and a $2$- approximation algorithm for trees. In this paper, we propose an approximation algorithm for trees that produces a burning sequence of length at most $\lfloor 1.75b(T) \rfloor + 1$, where $b(T)$ is length of the optimal burning sequence, also called the burning number of the tree $T$. In other words, we achieve an approximation factor of $(\lfloor 1.75b(T) \rfloor + 1)/b(T)$.
