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:

How fast can we reach a target vertex in stochastic temporal graphs?

Akrida, Eleni C. and Mertzios, George B. and Nikoletseas, Sotiris and Raptopoulos, Christoforos and Spirakis, Paul G. and Zmaraev, Viktor (2020) 'How fast can we reach a target vertex in stochastic temporal graphs?', Journal of computer and system sciences., 114 . pp. 65-83.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2020 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:04 May 2020
Date deposited:11 May 2020
Date of first online publication:28 May 2020
Date first made open access:28 May 2021

Save or Share this output

Look up in GoogleScholar