Combinatorial Aspects of Move-Up Crews for Spreading Processes on Networks

Marco Laumanns and Rico Zenklusen
Additional contact information
Marco Laumanns: Institute for Operations Research, ETH Zurich
Rico Zenklusen: Institute for Operations Research, ETH Zurich

Chapter 93 in Operations Research Proceedings 2008, 2009, pp 575-580 from Springer

Abstract: Summary Spreading processes on networks can often be mapped onto network reliability problems. The computational complexity of computing the probability that the spreading process reaches some given subset K of the nodes is well studied as it reduces to the classical K-terminal reliability problem. Often one is not interested in a particular set K, but more global properties of the spreading process, such as the expected spreading size or the probability of a large spreading. We show that the direct Monte Carlo approach is an FPRAS for the expected spreading size, but unless NP ⊆ BPP, there is no randomized constant-factor approximation for the probability of large spreadings. When nodes are weighted to represent their importance, we show that estimating the expected spreading impact is of the same computational complexity as estimating s-t reliability.

Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-00142-0_93

Ordering information: This item can be ordered from
http://www.springer.com/9783642001420

DOI: 10.1007/978-3-642-00142-0_93

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().