Approximation algorithms for the firefighter problem: cuts over time and submodularity

DOI10.1007/978-3-642-10631-6_98MaRDI QIDQ3652284zbMATH OpenOpenAlexFDO

Authors Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, Chaitanya Swamy

Publication date 17 December 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-10631-6_98

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Approximation algorithms (68W25) Epidemiology (92D30)

Recommendations

• Approximability of the firefighter problem. Computing cuts over time
• Towards more efficient infection and fire fighting
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Resource minimization for fire containment
• The firefighter problem: empirical results on random graphs

Cited in

(12)

• Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results
• The firefighter problem with more than one firefighter on trees
• Approximability of the firefighter problem. Computing cuts over time
• Inoculation strategies for victims of viruses and the sum-of-squares partition problem
• On efficient vaccine distribution strategy to suppress pandemic using social relation
• Towards more efficient infection and fire fighting
• Continuous firefighting on infinite square grids
• The firefighter problem: empirical results on random graphs
• On the firefighter problem with spreading vaccination for maximizing the number of saved nodes: the IP model and LP rounding algorithms
• Target set selection in social networks with tiered influence and activation thresholds
• Exact solutions for the moving firefighter problem on trees
• The firefighter problem on graph classes

This page was built for publication: Approximation algorithms for the firefighter problem: cuts over time and submodularity

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