The firefighter problem on graph classes

DOI10.1016/J.TCS.2015.11.024MaRDI QIDQ899308zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Pinar Heggernes, 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

zbMATH Keywords

interval graphsfirefighter problempermutation graphssplit graphs\(P_k\)-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Parameterized Complexity of Firefighting Revisited
• scientific article; zbMATH DE number 2061798
• The Firefighter Problem: A Structural Analysis
• The firefighter problem with more than one firefighter on trees

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2061798 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
• Algorithmic graph theory and perfect graphs
• Approximation algorithms for the firefighter problem: cuts over time and submodularity
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Firefighting on trees: How bad is the greedy algorithm?
• Graph Classes: A Survey
• Modular decomposition and transitive orientation
• On rigid circuit graphs
• Parameterized Complexity of Firefighting Revisited
• Parameterized complexity of firefighting
• Parameterized complexity of the firefighter problem
• Resource minimization for fire containment
• Surviving rates of graphs with bounded treewidth for the firefighter problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Firefighter problem: a survey of results, directions and questions
• The firefighter problem for graphs of maximum degree three
• The splittance of a graph
• Treewidth and Pathwidth of Permutation Graphs

Cited in

(19)

• Politician’s Firefighting
• Firefighting on trees
• scientific article; zbMATH DE number 2061798 (Why is no real title available?)
• The firefighter problem for cubic graphs
• The firefighter problem: saving sets of vertices on cubic graphs
• On the firefighter problem of full icosahedral symmetry fullerene graphs
• The firefighter problem with more than one firefighter on trees
• Firefighting on trees and Cayley graphs
• Saving critical nodes with firefighters is FPT
• Parameterized complexity of firefighting
• Establishing herd immunity is hard even in simple geometric networks
• New integrality gap results for the firefighters problem on trees
• A new model and algorithms in firefighting theory
• The Firefighter problem: a survey of results, directions and questions
• Orienting edges to fight fire in graphs
• scientific article; zbMATH DE number 1802810 (Why is no real title available?)
• Geometric firefighting in the half-plane
• The firefighter problem: empirical results on random graphs
• Fire Containment in Planar Graphs

This page was built for publication: The firefighter problem on graph classes

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