Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
From MaRDI portal
Publication:3596724
DOI10.1007/978-3-540-92182-0_25zbMath1183.05077MaRDI QIDQ3596724
Lin Yang, Elad Verbin, Leizhen Cai
Publication date: 29 January 2009
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92182-0_25
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
Related Items
On structural parameterizations of firefighting, Firefighting as a Strategic Game, A matheuristic for the firefighter problem on graphs, On the firefighter problem with spreading vaccination for maximizing the number of saved nodes: the IP model and LP rounding algorithms, Slash and burn on graphs -- firefighting with general weights, The firefighter problem: empirical results on random graphs, The firefighter problem: further steps in understanding its complexity, The firefighter problem on graph classes, The firefighter problem with more than one firefighter on trees, Surviving rate of graphs and firefighter problem, Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment, Firefighting on trees, Approximation algorithms for the geometric firefighter and budget fence problems, Asymptotic surviving rate of trees with multiple fire sources, Approximability of the firefighter problem. Computing cuts over time, More fires and more fighters, Parameterized complexity of firefighting, Multi-layered planar firefighting, Parameterized Complexity of Firefighting Revisited, The Firefighter Problem: A Structural Analysis, New Integrality Gap Results for the Firefighters Problem on Trees, Continuous Firefighting on Infinite Square Grids