The firefighter problem: further steps in understanding its complexity
From MaRDI portal
Publication:527402
DOI10.1016/j.tcs.2017.03.004zbMath1370.68118OpenAlexW2595377643MaRDI QIDQ527402
Morgan Chopin, Janka Chlebíková
Publication date: 11 May 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hal.sorbonne-universite.fr/hal-01504559/file/Chlebikova_The_firefighter.pdf
Analysis of algorithms and problem complexity (68Q25) Games on graphs (graph-theoretic aspects) (05C57)
Related Items (3)
Surviving rate of graphs and firefighter problem ⋮ On structural parameterizations of firefighting ⋮ Firefighting on trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The firefighter problem for cubic graphs
- Fixed-parameter algorithms for cluster vertex deletion
- 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
- The Firefighter Problem: A Structural Analysis
- New Integrality Gap Results for the Firefighters Problem on Trees
- Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
- Firefighting on Trees Beyond Integrality Gaps
This page was built for publication: The firefighter problem: further steps in understanding its complexity
