The firefighter problem: further steps in understanding its complexity

DOI10.1016/J.TCS.2017.03.004MaRDI QIDQ527402zbMATH OpenOpenAlexFDO

Authors Janka Chlebíková, Morgan Chopin

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

firefighter problemparameterized complexitypathwidthtrees

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Firefighter Problem: A Structural Analysis
• The Firefighter problem: a survey of results, directions and questions
• scientific article; zbMATH DE number 2061798
• Parameterized complexity of the firefighter problem
• An analysis of the weighted firefighter problem
• Parameterized Complexity of Firefighting Revisited
• Parameterized complexity of firefighting
• Finding exact solutions for the geometric firefighter problem in practice
• Approximability of the firefighter problem. Computing cuts over time

Cites work

• A generalization of the firefighter problem on \(\mathbb Z \times \mathbb Z\)
• Approximability of the firefighter problem. Computing cuts over time
• Cluster vertex deletion: a parameterization between vertex cover and clique-width
• Fire containment in grids of dimension three and higher
• Firefighting on trees beyond integrality gaps
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Firefighting on trees: How bad is the greedy algorithm?
• Fixed-parameter algorithms for cluster vertex deletion
• Graphs with small bandwidth and cutwidth
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2061798 (Why is no real title available?)
• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• More fires and more fighters
• New integrality gap results for the firefighters problem on trees
• Parameterized complexity of firefighting
• The firefighter problem for cubic graphs
• The firefighter problem for graphs of maximum degree three
• The firefighter problem with more than one firefighter on trees
• The Firefighter Problem: A Structural Analysis
• Tree-width, path-width, and cutwidth

Cited in

(9)

• Surviving rate of graphs and firefighter problem
• Firefighting on trees
• Parameterized Complexity of Firefighting Revisited
• The Firefighter Problem: A Structural Analysis
• Parameterized complexity of the firefighter problem
• The firebreak problem
• Space-efficient parameterized algorithms on graphs of low shrubdepth
• Bandwidth parameterized by cluster vertex deletion number
• Exact solutions for the moving firefighter problem on trees

This page was built for publication: The firefighter problem: further steps in understanding its complexity

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