Computational complexity of impact size estimation for spreading processes on networks

DOI10.1140/epjb/e2009-00344-7zbMath1188.90282MaRDI QIDQ977764

Marco Laumanns, Rico Zenklusen

Publication date: 23 June 2010

Published in: The European Physical Journal B. Condensed Matter and Complex Systems (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/19034

zbMATH Keywords

computational complexity; networks; complex systems; justifications or modifications of Monte Carlo methods

Mathematics Subject Classification ID

05C82: Small world graphs, complex networks (graph-theoretic aspects)

90C60: Abstract computational complexity for mathematical programming problems

68R10: Graph theory (including graph drawing) in computer science

Related Items

Finding the probability of infection in an SIR network is NP-hard

Cites Work

• Unnamed Item
• On the critical behavior of the general epidemic process and dynamical percolation
• Reaction-diffusion processes and epidemic metapopulation models in complex networks
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Network reliability and the probabilistic estimation of damage from fire spread
• Thresholds for virus spread on networks
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Bounding the Size and Probability of Epidemics on Networks
• A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• The Complexity of Enumeration and Reliability Problems
• Complexity of network reliability computations
• Optimal Reduction of Two-Terminal Directed Acyclic Graphs
• The Delta-Wye Approximation Procedure for Two-Terminal Reliability
• An Optimal Algorithm for Monte Carlo Estimation
• Renormalization of two—terminal reliability
• Counting over non-planar graphs