The firefighter problem for graphs of maximum degree three

DOI10.1016/J.DISC.2005.12.053MaRDI QIDQ2370449zbMATH OpenOpenAlexFDO

Authors Stephen Finbow, Gary MacGillivray, Romeo Rizzi, Andrew D. King

Publication date 26 June 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.12.053

zbMATH Keywords

firefigher problemNP-complete problemoptimization on graphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The firefighter problem for cubic graphs
• scientific article; zbMATH DE number 2061798
• The firefighter problem: saving sets of vertices on cubic graphs
• The firefighter problem with more than one firefighter on trees
• The Firefighter Problem: A Structural Analysis

Cites work

• Firefighting on trees: How bad is the greedy algorithm?
• scientific article; zbMATH DE number 1802810 (Why is no real title available?)
• 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 1506515 (Why is no real title available?)
• scientific article; zbMATH DE number 975407 (Why is no real title available?)
• On designing a network to defend against random attacks of radius two
• On minimal neighbourhood-connected graphs

Cited in

(61)

• Finding exact solutions for the geometric firefighter problem in practice
• Planar graphs without chordal 5-cycles are 2-good
• Solving the geometric firefighter routing problem via integer programming
• The firefighter problem with more than one firefighter on trees
• A lower bound of the surviving rate of a planar graph with girth at least seven
• On perturbation resilience of non-uniform k-center
• Complexity of the multilevel critical node problem
• Surviving rate of graphs and firefighter problem
• Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment
• Firefighting on trees
• Approximation algorithms for the geometric firefighter and budget fence problems
• Asymptotic surviving rate of trees with multiple fire sources
• Burning a graph is hard
• Approximability of the firefighter problem. Computing cuts over time
• More fires and more fighters
• Parameterized complexity of firefighting
• A generalization of the firefighter problem on \(\mathbb Z \times \mathbb Z\)
• Multi-layered planar firefighting
• The 2-surviving rate of planar graphs without 5-cycles
• Towards more efficient infection and fire fighting
• Defending planar graphs against star-cutsets
• Parameterized Complexity of Firefighting Revisited
• The Firefighter Problem: A Structural Analysis
• Continuous firefighting on infinite square grids
• Slash and burn on graphs -- firefighting with general weights
• The firefighter problem: empirical results on random graphs
• The 2-surviving rate of planar graphs without 6-cycles
• The surviving rate of digraphs
• scientific article; zbMATH DE number 2061798 (Why is no real title available?)
• Orienting edges to fight fire in graphs
• Firefighting on square, hexagonal, and triangular grids
• A note on the surviving rate of 1-planar graphs
• The firefighter problem: saving sets of vertices on cubic graphs
• The firefighter problem: further steps in understanding its complexity
• Fire Containment in Planar Graphs
• On a fire fighter's problem
• How to Burn a Graph
• Firefighting as a strategic game
• Geometric firefighting in the half-plane
• Robust \(k\)-center with two types of radii
• Robust \(k\)-center with two types of radii
• scientific article; zbMATH DE number 7758333 (Why is no real title available?)
• A matheuristic for the firefighter problem on graphs
• On the predictability of the abelian sandpile model
• The surviving rate of an outerplanar graph for the firefighter problem
• The burning of the snark
• Slim tree-cut width
• Distance-restricted firefighting on finite graphs
• Space-efficient parameterized algorithms on graphs of low shrubdepth
• The edge surviving rate of Halin graphs
• Slim tree-cut width
• Maximizing vertex rescue: investigating the firefighter problem with edge subdivision
• The surviving rate of an infected network
• The 2-surviving rate of planar graphs without 4-cycles
• Exact solutions for the moving firefighter problem on trees
• Advancing firefighter games: novel integer programming formulations and the cost-value model
• Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly
• The surviving rate of planar graphs
• The firefighter problem on graph classes
• The firefighter problem for cubic graphs
• Galaxy cutsets in graphs

This page was built for publication: The firefighter problem for graphs of maximum degree three

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