Probability of infection in SIR networks is NP-hard
Edgar Delgado-EckertMichael ShapiroPublished in: CoRR (2010)
Keyphrases
- np hard
- special case
- optimal solution
- probability distribution
- cellular networks
- linear programming
- lower bound
- social networks
- data sets
- network analysis
- sir model
- approximation algorithms
- network structure
- constraint satisfaction problems
- np complete
- scheduling problem
- closely related
- decision problems
- complex networks
- network model
- np hardness
- set cover
- computational complexity