Title of article
New heuristics for burning connected graphs
Author/Authors
Tahmasbi, Maryam Department of Computer and Data Sciences - Shahid Beheshti University, Tehran, Iran , Rezai Farokh, Zahra Department of Computer and Data Sciences - Shahid Beheshti University, Tehran, Iran , Buali, Yousof Department of Computer and Data Sciences - Shahid Beheshti University, Tehran, Iran , Haj Rajab Ali Tehrani, Zahra Department of Computer and Data Sciences - Shahid Beheshti University, Tehran, Iran
Pages
8
From page
165
To page
172
Abstract
The concept of graph burning and burning number (bn(G)) of a graph G was introduced recently [4]. Graph burning models the spread of contagion (re) 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 rst 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 -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 1000 random graphs with known distance to cluster and tested our heuristics on them.
Keywords
Burning number , Heuristic , Distance to cluster , θ-Graphs , DIMACS , BHOSLIB
Journal title
AUT Journal of Mathematics and Computing
Serial Year
2022
Record number
2727546
Link To Document