A new model in firefighting theory

DOI10.1007/978-3-030-39219-2_30zbMATH Open1453.68207arXiv1911.10341OpenAlexW3002346630MaRDI QIDQ779236FDOQ779236

Jörg-Rüdiger Sack, Barbara Schwarzwald, Elmar Langetepe, Rolf Klein, David Kübel

Publication date: 21 July 2020

Abstract: Continuous and discrete models for firefighting problems are well-studied in Theoretical Computer Science. We introduce a new, discrete, and more general framework based on a hexagonal cell graph to study firefighting problems in varied terrains. We present three different firefighting problems in the context of this model; for two of which, we provide efficient polynomial time algorithms and for the third, we show NP-completeness. We also discuss possible extensions of the model and their implications on the computational complexity.

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

Recommendations

• A new model and algorithms in firefighting theory
• A New Model in Flame Theory
• On structural parameterizations of firefighting
• On structural parameterizations of firefighting
• A NEW NUMERICAL APPROACH FOR FIRE SIMULATION
• Dynamic modelling of building fires
• A convection model for fire spread simulation
• scientific article; zbMATH DE number 1206144
• A fire emergency service location model

zbMATH Keywords

computational complexitygraph theorydiscrete geometrygraph algorithmsNP-completenesscellular automatonundecidabilitycombinatorial algorithmsfirefightingfire-behaviour modelingfire-spread modelsforest-fire simulationfrontal propagation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Cellular automata (computational aspects) (68Q80)

Cited In (4)

• Modeling Arson: An Exercise in Qualitative Model Building
• Title not available (Why is that?)
• A Comprehensive Definition of Fire Codes
• A new model and algorithms in firefighting theory

This page was built for publication: A new model in firefighting theory

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