The firefighter problem on graph classes

DOI10.1016/J.TCS.2015.11.024zbMATH Open1333.05290OpenAlexW2180255218WikidataQ60488383 ScholiaQ60488383MaRDI QIDQ899308FDOQ899308

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

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

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)

Cites Work

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

Cited In (19)

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

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)