New heuristics for burning connected graphs | ||
| AUT Journal of Mathematics and Computing | ||
| مقاله 5، دوره 3، شماره 2، آذر 2022، صفحه 165-172 اصل مقاله (408.81 K) | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22060/ajmc.2022.21692.1101 | ||
| نویسندگان | ||
| Maryam Tahmasbi* ؛ Zahra Rezai Farokh؛ Yousof Buali؛ Zahra Haj Rajab Ali Tehrani | ||
| Department of Computer and Data Sciences, Shahid Beheshti University, Tehran, Iran | ||
| چکیده | ||
| 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 (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 1000 random graphs with known distance to cluster and tested our heuristics on them. | ||
| کلیدواژهها | ||
| Burning number؛ Heuristic؛ Distance to cluster؛ $\theta$-Graphs؛ DIMACS؛ BHOSLIB | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 707 تعداد دریافت فایل اصل مقاله: 689 |
||
| تعداد نشریات | 9 |
| تعداد شمارهها | 455 |
| تعداد مقالات | 5,771 |
| تعداد مشاهده مقاله | 8,375,059 |
| تعداد دریافت فایل اصل مقاله | 6,933,326 |