The firefighter problem for graphs of maximum degree three
From MaRDI portal
Publication:2370449
DOI10.1016/j.disc.2005.12.053zbMath1120.68081OpenAlexW1976619117MaRDI QIDQ2370449
Romeo Rizzi, Stephen Finbow, Gary MacGillivray, 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (51)
Complexity of the multilevel critical node problem ⋮ The 2-surviving rate of planar graphs without 5-cycles ⋮ Parameterized Complexity of Firefighting Revisited ⋮ Slash and burn on graphs -- firefighting with general weights ⋮ Surviving rate of graphs and firefighter problem ⋮ The firefighter problem: empirical results on random graphs ⋮ Finding exact solutions for the geometric firefighter problem in practice ⋮ Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment ⋮ Fire Containment in Planar Graphs ⋮ Burning a graph is hard ⋮ The Firefighter Problem: A Structural Analysis ⋮ The 2-surviving rate of planar graphs without 6-cycles ⋮ The surviving rate of digraphs ⋮ Multi-layered planar firefighting ⋮ A matheuristic for the firefighter problem on graphs ⋮ The firefighter problem on graph classes ⋮ The surviving rate of an outerplanar graph for the firefighter problem ⋮ On the predictability of the abelian sandpile model ⋮ Approximability of the firefighter problem. Computing cuts over time ⋮ The firefighter problem with more than one firefighter on trees ⋮ Unnamed Item ⋮ More fires and more fighters ⋮ Firefighting on square, hexagonal, and triangular grids ⋮ On a Fire Fighter’s Problem ⋮ Continuous Firefighting on Infinite Square Grids ⋮ Parameterized complexity of firefighting ⋮ Planar graphs without chordal 5-cycles are 2-good ⋮ A note on the surviving rate of 1-planar graphs ⋮ A generalization of the firefighter problem on \(\mathbb Z \times \mathbb Z\) ⋮ Solving the geometric firefighter routing problem via integer programming ⋮ The firefighter problem: further steps in understanding its complexity ⋮ The firefighter problem for cubic graphs ⋮ Galaxy cutsets in graphs ⋮ The surviving rate of an infected network ⋮ A lower bound of the surviving rate of a planar graph with girth at least seven ⋮ The 2-surviving rate of planar graphs without 4-cycles ⋮ Geometric firefighting in the half-plane ⋮ Robust \(k\)-center with two types of radii ⋮ Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly ⋮ Robust \(k\)-center with two types of radii ⋮ On structural parameterizations of firefighting ⋮ The surviving rate of planar graphs ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ TOWARDS MORE EFFICIENT INFECTION AND FIRE FIGHTING ⋮ Unnamed Item ⋮ Firefighting on trees ⋮ Approximation algorithms for the geometric firefighter and budget fence problems ⋮ Defending Planar Graphs against Star-Cutsets ⋮ How to Burn a Graph ⋮ Firefighting as a Strategic Game ⋮ Asymptotic surviving rate of trees with multiple fire sources
Cites Work
This page was built for publication: The firefighter problem for graphs of maximum degree three
