J. Enright
Deleting edges to restrict the size of an epidemic in temporal networks
Enright, J.; Meeks, K.; Mertzios, G.B.; Zamaraev, V.
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 | Feb 12, 2022 |
Journal | Journal of Computer and System Sciences |
Print ISSN | 0022-0000 |
Electronic ISSN | 1090-2724 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 119 |
Pages | 60-77 |
DOI | https://doi.org/10.1016/j.jcss.2021.01.007 |
Public URL | https://durham-repository.worktribe.com/output/1246798 |
Files
Accepted Journal Article
(568 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright 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/
You might also like
The complexity of computing optimum labelings for temporal connectivity
(2022)
Presentation / Conference Contribution
The complexity of temporal vertex cover in small-degree graphs
(2022)
Presentation / Conference Contribution
The complexity of transitively orienting temporal graphs
(2021)
Presentation / Conference Contribution
Equitable scheduling on a single machine
(2021)
Presentation / Conference Contribution
Exact and approximate algorithms for computing a second Hamiltonian cycle
(2020)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search