论文标题
通过最远的遍历燃烧图
Burning graphs through farthest-first traversal
论文作者
论文摘要
图形燃烧问题是一个NP-硬化的组合优化问题，有助于量化图形与传染的脆弱性。本文通过一般图引入了此问题的最简单的最远的基于遍历的近似算法。我们将此提案称为最远的（BFF）算法。 BFF以$ O（n^3）$台阶运行，近似值为$ 3-2/b（g）$，其中$ b（g）$是最佳解决方案的大小。尽管它很简单，但在通过某些基准数据集进行测试时，BFF倾向于生成近乎最佳的解决方案。实际上，它返回了与文献中更详细的启发式方法回归的解决方案相似的解决方案。
The graph burning problem is an NP-hard combinatorial optimization problem that helps quantify the vulnerability of a graph to contagion. This paper introduces a simple farthest-first traversal-based approximation algorithm for this problem over general graphs. We refer to this proposal as the Burning Farthest-First (BFF) algorithm. BFF runs in $O(n^3)$ steps and has an approximation factor of $3-2/b(G)$, where $b(G)$ is the size of an optimal solution. Despite its simplicity, BFF tends to generate near-optimal solutions when tested over some benchmark datasets; in fact, it returns similar solutions to those returned by much more elaborated heuristics from the literature.
