Maximizing vertex rescue: investigating the firefighter problem with edge subdivision
Issued Date
2024-01-01
Resource Type
ISSN
09728600
Scopus ID
2-s2.0-85209690974
Journal Title
AKCE International Journal of Graphs and Combinatorics
Rights Holder(s)
SCOPUS
Bibliographic Citation
AKCE International Journal of Graphs and Combinatorics (2024)
Suggested Citation
Weeranukunjit C., Lewchalermvongs C. Maximizing vertex rescue: investigating the firefighter problem with edge subdivision. AKCE International Journal of Graphs and Combinatorics (2024). doi:10.1080/09728600.2024.2418643 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/102194
Title
Maximizing vertex rescue: investigating the firefighter problem with edge subdivision
Author(s)
Author's Affiliation
Corresponding Author(s)
Other Contributor(s)
Abstract
The firefighter problem is a game played on a connected graph where a fire breaks out at a vertex. In each round, a firefighter chooses a vertex to protect, and the fire then spreads to all unprotected neighbors of the burning vertex. This sequence continues until the fire can no longer spread. The objective is to maximize the number of saved vertices, necessitating a strategic approach by the firefighter. This problem serves as a simplistic model for scenarios such as disease spread in a network or people’s movement under specific circumstances. To simulate a scenario with limited resources, we introduce a new firefighter method, involving the protection of one vertex and subdividing one edge. This method, achieved by adding a new vertex to the edge, effectively delays the burning of the vertex connected to the edge, providing additional time for the firefighter to protect it. Our investigation delves into the firefighter problem with subdividing edges, focusing on specific graphs. Notably, we present an optimal strategy for a graph with a maximum degree at most three.