The firefighter problem on graph classes

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

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

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

Cited In (9)

• Firefighting on trees
• Fire Containment in Planar Graphs
• Title not available (Why is that?)
• Establishing herd immunity is hard even in simple geometric networks
• Geometric firefighting in the half-plane
• Title not available (Why is that?)
• Firefighting on trees and Cayley graphs
• On structural parameterizations of firefighting
• 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)