Approximability of the firefighter problem. Computing cuts over time

DOI10.1007/s00453-010-9469-yzbMath1236.68291OpenAlexW2023624817MaRDI QIDQ2428668

Deeparnab Chakrabarty, Elliot Anshelevich, Chaitanya Swamy, Ameya Hate

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9469-y

zbMATH Keywords

submodularapproximation algorithmsvaccinationfirefightergraph cuts

Mathematics Subject Classification ID

Epidemiology (92D30) Applications of graph theory (05C90) Approximation algorithms (68W25)

Related Items (14)

A randomized algorithm with local search for containment of pandemic disease spread ⋮ The firefighter problem: empirical results on random graphs ⋮ Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment ⋮ The Firefighter Problem: A Structural Analysis ⋮ A matheuristic for the firefighter problem on graphs ⋮ New Integrality Gap Results for the Firefighters Problem on Trees ⋮ The firefighter problem: further steps in understanding its complexity ⋮ On efficient vaccine distribution strategy to suppress pandemic using social relation ⋮ APX-hardness and approximation for the \(k\)-burning number problem ⋮ APX-hardness and approximation for the \(k\)-burning number problem ⋮ Firefighting on trees ⋮ Approximation algorithms for the geometric firefighter and budget fence problems ⋮ Firefighting as a Strategic Game ⋮ Approximation algorithms for fragmenting a graph against a stochastically-located threat

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• The firefighter problem for graphs of maximum degree three
• Fire containment in grids of dimension three and higher
• Cut problems in graphs with a budget constraint
• Inoculation strategies for victims of viruses and the sum-of-squares partition problem
• A threshold of ln n for approximating set cover
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Length-Bounded Cuts and Flows
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Collective dynamics of ‘small-world’ networks
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Algorithms – ESA 2005
• Automata, Languages and Programming

This page was built for publication: Approximability of the firefighter problem. Computing cuts over time