Inoculation strategies for victims of viruses and the sum-of-squares partition problem

DOI10.1016/j.jcss.2006.02.003zbMath1100.68073OpenAlexW2025392770MaRDI QIDQ2507699

Yanyan Li

Publication date: 5 October 2006

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2006.02.003

zbMATH Keywords

price of anarchycomputer virus modelsecurity externalitieseconomics of securitysum-of-squares partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Games involving graphs (91A43) Applications of game theory (91A80) Graph theory (including graph drawing) in computer science (68R10) (n)-person games, (n>2) (91A06) Distributed systems (68M14) Approximation algorithms (68W25)

Related Items

Individual security, contagion, and network design ⋮ Network Elicitation in Adversarial Environment ⋮ Computing Critical Nodes in Directed Graphs ⋮ Bio-inspired paradigms in network engineering games ⋮ On the firefighter problem with spreading vaccination for maximizing the number of saved nodes: the IP model and LP rounding algorithms ⋮ Strategic Network Formation with Attack and Immunization ⋮ Approximability of the firefighter problem. Computing cuts over time ⋮ Strategic multiway cut and multicut games ⋮ Dynamic Games for Analyzing Competition in the Internet and in On-Line Social Networks ⋮ Optimal strategies for selecting coordinators ⋮ Contrasting the Spread of Misinformation in Online Social Networks ⋮ Defending against multiple different attackers ⋮ Connected subgraph defense games ⋮ How Do You Defend a Network? ⋮ On the inapproximability of minimizing cascading failures under the deterministic threshold model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mathematical modeling in epidemiology
• Interdependent security
• On the hardness of approximating Multicut and Sparsest-Cut
• A Polylogarithmic Approximation of the Minimum Bisection
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On the power of unique 2-prover 1-round games
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Fast Approximate Graph Partitioning Algorithms
• Expander flows, geometric embeddings and graph partitioning