The firefighter problem: further steps in understanding its complexity

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

zbMATH Keywords

treespathwidthparameterized complexityfirefighter problem

Mathematics Subject Classification ID

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