Back to Search Start Over

Approximation algorithms for the graph burning on cactus and directed trees.

Authors :
Gautam, Rahul Kumar
Kare, Anjeneya Swami
Bhavani, S. Durga
Source :
Discrete Mathematics, Algorithms & Applications. Oct2024, Vol. 16 Issue 7, p1-20. 20p.
Publication Year :
2024

Abstract

Given a graph G = (V , E) , the problem of Graph Burning is to find a sequence of nodes from V , called a burning sequence, to burn the whole graph. This is a discrete-step process, and at each step, an unburned vertex is selected as an agent to spread fire to its neighbors by marking it as a burnt node. A burnt node spreads the fire to its neighbors at the next consecutive step. The goal is to find the burning sequence of minimum length. The Graph Burning problem is NP-Hard for general graphs and even for binary trees. A few approximation results are known, including a 3 -approximation algorithm for general graphs and a 2 -approximation algorithm for trees. The Graph Burning on directed graphs is more challenging than on undirected graphs. In this paper, we propose (1) A 2. 7 5 -approximation algorithm for a cactus graph (undirected), (2) A 3 -approximation algorithm for multi-rooted directed trees (polytree) and (3) A 1. 9 0 5 -approximation algorithm for the single-rooted directed tree (arborescence). We implement all three approximation algorithms, and the results are shown for randomly generated cactus graphs, multi-rooted directed trees and single-rooted directed trees. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
17938309
Volume :
16
Issue :
7
Database :
Academic Search Index
Journal :
Discrete Mathematics, Algorithms & Applications
Publication Type :
Academic Journal
Accession number :
179965399
Full Text :
https://doi.org/10.1142/S1793830923500969