The Firefighter Problem: A Structural Analysis
From MaRDI portal
Publication:2946017
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
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