Towards more efficient infection and fire fighting

DOI10.1142/S0129054113400017MaRDI QIDQ2841981zbMATH OpenOpenAlexFDO

Authors Peter Floderus, Mia Persson, Andrzej Lingas

Publication date 30 July 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054113400017

zbMATH Keywords

approximation algorithmssubexponential algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Recommendations

• Approximation algorithms for the firefighter problem: cuts over time and submodularity
• Approximability of the firefighter problem. Computing cuts over time
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• 3/2 firefighters are not enough
• The firefighter problem: empirical results on random graphs

Cites work

• A Separator Theorem for Planar Graphs
• On the Number of Husimi Trees
• The budgeted maximum coverage problem
• The firefighter problem for graphs of maximum degree three

Cited in

(12)

• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Approximability of the firefighter problem. Computing cuts over time
• Parameterized Complexity of Firefighting Revisited
• Inoculation strategies for victims of viruses and the sum-of-squares partition problem
• Planar graph is on fire
• Parameterized complexity of firefighting
• Firefighting as a strategic game
• scientific article; zbMATH DE number 1506515 (Why is no real title available?)
• On the firefighter problem with spreading vaccination for maximizing the number of saved nodes: the IP model and LP rounding algorithms
• Approximation algorithms for the geometric firefighter and budget fence problems
• Approximation algorithms for the firefighter problem: cuts over time and submodularity
• Approximations of the generalized cascade model

This page was built for publication: Towards more efficient infection and fire fighting

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