The Complexity and Approximability of Minimum Contamination Problems

DOI10.1007/978-3-642-20877-5_30zbMath1331.68093OpenAlexW1516979601MaRDI QIDQ3010410

Lin-Qing Tang, Ang Sheng Li

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_30

Mathematics Subject Classification ID

Epidemiology (92D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ A derandomized approximation algorithm for the critical node detection problem ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ Assigning times to minimise reachability in temporal graphs

Cites Work

• Unnamed Item
• On the hardness of optimization in power-law graphs
• Covering a Graph with a Constrained Forest (Extended Abstract)
• The Complexity of Multiterminal Cuts
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications