The complexity and approximability of minimum contamination problems

DOI10.1007/978-3-642-20877-5_30MaRDI QIDQ3010410zbMATH OpenOpenAlexFDO

Authors Lin-Qing Tang, Angsheng 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)

Recommendations

• Computational complexity of the graph approximation problem
• On the hardness of approximating minimization problems
• Algorithms – ESA 2004
• Complexity of approximating bounded variants of optimization problems
• On the hardness of approximating minimum vertex cover

Cites work

• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Covering a graph with a constrained forest (extended abstract)
• Inoculation strategies for victims of viruses and the sum-of-squares partition problem
• On the hardness of optimization in power-law graphs
• The Complexity of Multiterminal Cuts

Cited in

(5)

• A derandomized approximation algorithm for the critical node detection problem
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Assigning times to minimise reachability in temporal graphs
• Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem

This page was built for publication: The complexity and approximability of minimum contamination problems

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