New heuristics for burning connected graphs
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 heu...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Amirkabir University of Technology
2022-09-01
|
| Series: | AUT Journal of Mathematics and Computing |
| Subjects: | |
| Online Access: | https://ajmc.aut.ac.ir/article_4911_40d37084dba40edae5928d8f7331634d.pdf |
| _version_ | 1827350062229880832 |
|---|---|
| author | Maryam Tahmasbi Zahra Rezai Farokh Yousof Buali Zahra Tehrani |
| author_facet | Maryam Tahmasbi Zahra Rezai Farokh Yousof Buali Zahra Tehrani |
| author_sort | Maryam Tahmasbi |
| collection | DOAJ |
| description | 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 θ-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. |
| first_indexed | 2024-03-08T00:52:21Z |
| format | Article |
| id | doaj.art-d6071d3e55bd4c478a1b6a7b0695ade3 |
| institution | Directory Open Access Journal |
| issn | 2783-2449 2783-2287 |
| language | English |
| last_indexed | 2024-03-08T00:52:21Z |
| publishDate | 2022-09-01 |
| publisher | Amirkabir University of Technology |
| record_format | Article |
| series | AUT Journal of Mathematics and Computing |
| spelling | doaj.art-d6071d3e55bd4c478a1b6a7b0695ade32024-02-14T19:38:44ZengAmirkabir University of TechnologyAUT Journal of Mathematics and Computing2783-24492783-22872022-09-013216517210.22060/ajmc.2022.21692.11014911New heuristics for burning connected graphsMaryam Tahmasbi0Zahra Rezai Farokh1Yousof Buali2Zahra Tehrani3Department of Computer and Data Sciences, Shahid Beheshti University, Tehran, IranDepartment of Computer and Data Sciences, Shahid Beheshti University, Tehran, IranDepartment of Computer and Data Sciences, Shahid Beheshti University, Tehran, IranDepartment of Computer and Data Sciences, Shahid Beheshti University, Tehran, IranThe 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 θ-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.https://ajmc.aut.ac.ir/article_4911_40d37084dba40edae5928d8f7331634d.pdfburning numberheuristicdistance to clusterθ-graphsdimacsbhoslib |
| spellingShingle | Maryam Tahmasbi Zahra Rezai Farokh Yousof Buali Zahra Tehrani New heuristics for burning connected graphs AUT Journal of Mathematics and Computing burning number heuristic distance to cluster θ-graphs dimacs bhoslib |
| title | New heuristics for burning connected graphs |
| title_full | New heuristics for burning connected graphs |
| title_fullStr | New heuristics for burning connected graphs |
| title_full_unstemmed | New heuristics for burning connected graphs |
| title_short | New heuristics for burning connected graphs |
| title_sort | new heuristics for burning connected graphs |
| topic | burning number heuristic distance to cluster θ-graphs dimacs bhoslib |
| url | https://ajmc.aut.ac.ir/article_4911_40d37084dba40edae5928d8f7331634d.pdf |
| work_keys_str_mv | AT maryamtahmasbi newheuristicsforburningconnectedgraphs AT zahrarezaifarokh newheuristicsforburningconnectedgraphs AT yousofbuali newheuristicsforburningconnectedgraphs AT zahratehrani newheuristicsforburningconnectedgraphs |