The firefighter problem with more than one firefighter on trees

DOI10.1016/j.dam.2012.11.011zbMath1263.05068arXiv1110.0341OpenAlexW2093573708MaRDI QIDQ1949095

Cristina Bazgan, Morgan Chopin, Bernard Ries

Publication date: 25 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complexityapproximationtreesfirefighter problemcaterpillars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

The 2-surviving rate of planar graphs without 5-cycles ⋮ Slash and burn on graphs -- firefighting with general weights ⋮ The firefighter problem: empirical results on random graphs ⋮ The Firefighter Problem: A Structural Analysis ⋮ New Integrality Gap Results for the Firefighters Problem on Trees ⋮ More fires and more fighters ⋮ Parameterized complexity of firefighting ⋮ Planar graphs without chordal 5-cycles are 2-good ⋮ The firefighter problem: further steps in understanding its complexity ⋮ The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation ⋮ APX-hardness and approximation for the \(k\)-burning number problem ⋮ APX-hardness and approximation for the \(k\)-burning number problem ⋮ Firefighting on trees ⋮ Firefighting as a Strategic Game

Cites Work

• The firefighter problem for cubic graphs
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• The firefighter problem for graphs of maximum degree three
• Fire containment in grids of dimension three and higher
• A generalization of the firefighter problem on \(\mathbb Z \times \mathbb Z\)
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity
• Politician’s Firefighting
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The firefighter problem with more than one firefighter on trees