The firefighter problem with more than one firefighter on trees

DOI10.1016/j.dam.2012.11.011zbMath1263.05068arXiv1110.0341MaRDI 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

complexity; approximation; trees; firefighter problem; caterpillars

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

APX-hardness and approximation for the \(k\)-burning number problem, APX-hardness and approximation for the \(k\)-burning number problem, Firefighting as a Strategic Game, 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: further steps in understanding its complexity, Planar graphs without chordal 5-cycles are 2-good, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, Firefighting on trees, More fires and more fighters, Parameterized complexity of firefighting, The Firefighter Problem: A Structural Analysis, New Integrality Gap Results for the Firefighters Problem on Trees

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