Skip to main content

Research Repository

Advanced Search

Deleting edges to restrict the size of an epidemic in temporal networks

Enright, J.; Meeks, K.; Mertzios, G.B.; Zamaraev, V.

Deleting edges to restrict the size of an epidemic in temporal networks Thumbnail


Authors

J. Enright

K. Meeks

V. Zamaraev



Abstract

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes spread are dynamic in nature, and can be modeled with temporal graphs. Here, we study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path. We introduce a natural edge-deletion problem for temporal graphs and provide positive and negative results on its computational complexity and approximability.

Citation

Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2021). Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences, 119, 60-77. https://doi.org/10.1016/j.jcss.2021.01.007

Journal Article Type Article
Acceptance Date Jan 29, 2021
Online Publication Date Feb 12, 2021
Publication Date 2021-08
Deposit Date Feb 9, 2021
Publicly Available Date Mar 28, 2024
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 119
Pages 60-77
DOI https://doi.org/10.1016/j.jcss.2021.01.007

Files





You might also like



Downloadable Citations