A graph theoretical approach to the firebreak locating problem

DOI10.1016/J.TCS.2022.02.012MaRDI QIDQ2124231zbMATH OpenOpenAlexFDO

Authors Marc Demange, Alessia Di Fonso, Gabriele Di Stefano, Pierpaolo Vittorini

Publication date 19 April 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.10115

zbMATH Keywords

risk managementNP-hardnessplanar graphsfirebreak locationrestricted planar Max 2-SATwildfire emergency management

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Discrete location and assignment (90B80)

Abstract: In the last decade, wildfires have become wider and more destructive. The climate change and the growth of urban areas may further increase the probability of incidence of large-scale fires. The risk of fire can be lowered with preventive measures. Among them, firefighting lines are used to stop the fire from spreading beyond them. Due to high costs of installation and maintenance, their placement must be carefully planned. In this work, we address the wildfire management problem from a theoretical point of view and define a risk function to model the fire diffusion phenomena. The land is modeled by a mixed graph in which vertices are areas subject to fire with a certain probability while edges model the probability of fire spreading from one area to another. To reduce the risk, we introduce the {sc Windy Firebreak Location} problem that addresses the optimal positioning of firefighting lines under budget constraints. We study the complexity of the problem and prove its hardness even when the graph is planar, bipartite, with maximum degree four and the propagation probabilities are equal to one. We also show an efficient polynomial time algorithm for particular instances on trees.

Recommendations

• The firefighter problem: empirical results on random graphs
• Politician’s Firefighting
• Approximation algorithms for fragmenting a graph against a stochastically-located threat
• A new model and algorithms in firefighting theory
• The Firefighter problem: a survey of results, directions and questions

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 193169 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• An individual-based networked model with probabilistic relocation of people and vectors among locations for simulating the spread of infectious diseases
• General theoretical results on rectilinear embeddability of graphs
• Minimum bisection is NP-hard on unit disk graphs
• Planar Formulae and Their Uses
• Some simplified NP-complete graph problems
• The Complexity of Multiterminal Cuts
• The Complexity of Reliability Computations in Planar and Acyclic Graphs

Cited in

(4)

• The firebreak problem
• A robust \(p\)-center problem under pressure to locate shelters in wildfire context
• Approximation algorithms for fragmenting a graph against a stochastically-located threat
• Fire Containment in Planar Graphs

This page was built for publication: A graph theoretical approach to the firebreak locating problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2124231)