论文标题
燃烧图的新启发式方法
New heuristics for burning graphs
论文作者
论文摘要
最近引入了图G的图形燃烧和燃烧数字（$ bn（g）$）的概念[1]。图形燃烧模型在离散时间步骤中图中传播（火）的传播。 $ bn（g）$是燃烧图形$ g $所需的最低时间。问题是NP完成。在本文中，我们开发了第一个启发式方法来解决该问题（连接）图。为了测试算法的性能，我们将它们应用于具有已知燃烧数字（例如Theta图）的一些图形类，我们测试了DIMAC和Bhoslib上的算法，这些算法是图理论中NP-HARD问题的基准。我们还改善了上界的上限，以在一般图上燃烧数量，以其与群集的距离。然后，我们生成了一个具有已知距离的2000个随机图的数据集以群集，并测试了我们对它们的启发式方法。
The concept of graph burning and burning number ($bn(G)$) of a graph G was introduced recently [1]. Graph burning models the spread of contagion (fire) in a graph in discrete time steps. $bn(G)$ is the minimum time needed to burn a graph $G$.The problem is NP-complete. In this paper, we develop first heuristics to solve the problem in general (connected) graphs. In order to test the performance of our algorithms, we applied them on some graph classes with known burning number such as theta graphs, we tested our algorithms on DIMACS and BHOSLIB that are known benchmarks for NP-hard problems in graph theory. We also improved the upper bound for burning number on general graphs in terms of their distance to cluster. Then we generated a data set of 2000 random graphs with known distance to cluster and tested our heuristics on them.
