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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (544Kb)
|Publisher Web site:||https://doi.org/10.1016/j.jcss.2020.05.005|
|Publisher 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/|
|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|