Skip to main content

Research Repository

Advanced Search

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

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


Sotiris Nikoletseas

Christoforos Raptopoulos

Paul G. Spirakis

Viktor Zmaraev


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.


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.

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


You might also like

Downloadable Citations