A graph theoretical approach to the firebreak locating problem

DOI10.1016/J.TCS.2022.02.012zbMATH Open1487.68124arXiv2103.10115OpenAlexW3139374507MaRDI QIDQ2124231FDOQ2124231

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Planar Formulae and Their Uses
• The Complexity of Multiterminal Cuts
• Some simplified NP-complete graph problems
• Title not available (Why is that?)
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• General theoretical results on rectilinear embeddability of graphs
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• Title not available (Why is that?)
• Minimum bisection is NP-hard on unit disk graphs
• AN INDIVIDUAL-BASED NETWORKED MODEL WITH PROBABILISTIC RELOCATION OF PEOPLE AND VECTORS AMONG LOCATIONS FOR SIMULATING THE SPREAD OF INFECTIOUS DISEASES

Cited In (2)

• Fire Containment in Planar Graphs
• The firebreak problem

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)