Date of Award

10-28-2024

Publication Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Computational Geometry;Firefighter Problem;Graph Burning

Supervisor

Ahmad Biniaz

Abstract

With the increasing usage of social media, the spread of information has become abundant. However, this surge in accessible news and updates has also heightened the risk of spreading rumors. In our research, we explore two problems related to this phenomenon: the graph burning problem and the firefighter problem. We provide a comprehensive survey of the graph burning problem, a discrete time process. Initially, all the vertices of the graph are unburned, and we start the fire at a single vertex. The fire then spreads to the adjacent vertices of the burned vertices, and at each step, we select a new vertex to burn. Our objective is to burn all the vertices in a minimum number of steps. The graph burning problem is NPComplete. We review various approximation algorithms and bounds, highlighting significant advancements over the past decade. In the firefighter problem, a graph is given, and a fire starts from a subset of vertices. At each step, firefighters protect a certain number of vertices as the fire continues to spread to adjacent vertices.

Download

Share

COinS