Dr Eleni Akrida eleni.akrida@durham.ac.uk
Associate Professor
How fast can we reach a target vertex in stochastic temporal graphs?
Akrida, Eleni C.; Mertzios, George B.; Nikoletseas, Sotiris; Raptopoulos, Christoforos; Spirakis, Paul G.; Zmaraev, Viktor
Authors
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Sotiris Nikoletseas
Christoforos Raptopoulos
Paul G. Spirakis
Viktor Zmaraev
Abstract
Temporal graphs abstractly model real-life inherently dynamic networks. Given a graph G, a temporal graph with G as the underlying graph is a sequence of subgraphs (snapshots) of G, where . In this paper we study stochastic temporal graphs, i.e. stochastic processes whose random variables are the snapshots of a temporal graph on G. A natural feature observed in various real-life scenarios is a memory effect in the appearance probabilities of particular edges; i.e. the probability an edge appears at time step t depends on its appearance (or absence) at the previous k steps. We study the hierarchy of models of memory-k, , in an edge-centric network evolution setting: every edge of G has its own independent probability distribution for its appearance over time. We thoroughly investigate the complexity of two naturally related, but fundamentally different, temporal path problems, called Minimum Arrival and Best Policy.
Citation
Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Raptopoulos, C., Spirakis, P. G., & Zmaraev, V. (2020). How fast can we reach a target vertex in stochastic temporal graphs?. Journal of Computer and System Sciences, 114, 65-83. https://doi.org/10.1016/j.jcss.2020.05.005
Journal Article Type | Article |
---|---|
Acceptance Date | May 4, 2020 |
Online Publication Date | May 28, 2020 |
Publication Date | Dec 1, 2020 |
Deposit Date | May 8, 2020 |
Publicly Available Date | May 28, 2021 |
Journal | Journal of Computer and System Sciences |
Print ISSN | 0022-0000 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 114 |
Pages | 65-83 |
DOI | https://doi.org/10.1016/j.jcss.2020.05.005 |
Files
Accepted Journal Article
(556 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2020 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
Narrowing and Stretching: Addressing the Challenge of Multi-track Programming
(2022)
Conference Proceeding
Connected Subgraph Defense Games
(2021)
Journal Article
The temporal explorer who returns to the base
(2021)
Journal Article
Connected Subgraph Defense Games
(2019)
Book Chapter
Temporal vertex cover with a sliding time window
(2019)
Journal Article
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