The Firefighter Problem: A Structural Analysis

DOI10.1007/978-3-319-13524-3_15zbMath1457.68124arXiv1310.2322OpenAlexW2964351140MaRDI QIDQ2946017

Morgan Chopin, Janka Chlebíková

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

Surviving rate of graphs and firefighter problem ⋮ New Integrality Gap Results for the Firefighters Problem on Trees ⋮ The firefighter problem: further steps in understanding its complexity ⋮ Firefighting as a Strategic Game

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The firefighter problem for cubic graphs
• Graphs with small bandwidth and cutwidth
• Tree-width, path-width, and cutwidth
• The firefighter problem with more than one firefighter on trees
• The firefighter problem for graphs of maximum degree three
• Approximability of the firefighter problem. Computing cuts over time
• More fires and more fighters
• Parameterized complexity of firefighting
• Fire containment in grids of dimension three and higher
• A generalization of the firefighter problem on \(\mathbb Z \times \mathbb Z\)
• Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm

This page was built for publication: The Firefighter Problem: A Structural Analysis