The firefighter problem on graph classes
From MaRDI portal
Publication:899308
DOI10.1016/j.tcs.2015.11.024zbMath1333.05290OpenAlexW2180255218WikidataQ60488383 ScholiaQ60488383MaRDI QIDQ899308
Pinar Heggernes, Fedor V. Fomin, Erik Jan van Leeuwen
Publication date: 28 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.11.024
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (5)
A new model and algorithms in firefighting theory ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Geometric firefighting in the half-plane ⋮ On structural parameterizations of firefighting ⋮ Firefighting on trees
Cites Work
- On rigid circuit graphs
- The splittance of a graph
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Modular decomposition and transitive orientation
- A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
- Algorithmic graph theory and perfect graphs
- The firefighter problem for graphs of maximum degree three
- Parameterized complexity of firefighting
- Parameterized Complexity of Firefighting Revisited
- Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem
- Parameterized Complexity of the Firefighter Problem
- 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
- A Linear Recognition Algorithm for Cographs
- Graph Classes: A Survey
- Treewidth and Pathwidth of Permutation Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The firefighter problem on graph classes
