Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

Enright, J. and Meeks, K. and Mertzios, G.B. and Zamaraev, V. (2021) 'Deleting edges to restrict the size of an epidemic in temporal networks.', Journal of computer and system sciences., 119 . pp. 60-77.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
Download PDF
(556Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.jcss.2021.01.007
Publisher statement:© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:29 January 2021
Date deposited:10 February 2021
Date of first online publication:12 February 2021
Date first made open access:12 February 2022

Save or Share this output

Export:
Export
Look up in GoogleScholar