How fast can we reach a target vertex in stochastic temporal graphs? (Q2194859): Difference between revisions

A temporal graph (or evolving graph) is a sequence of spanning subgraphs \((G_t : t \in {\mathbb N})\) of an underlying graph \(G\). One subgraph in the sequence is a \textit{snapshot}. A \textit{stochastic temporal graph} is a stochastic process on snapshots, forming a temporal graph on \(G\). This paper considers processes in which the probability that each edge \(e\in E\) appears at time step \(t\) depends on its status in the previous \(k\) steps. Edges behave independently of one another over time, each with its own probability distribution. A detailed examination of the complexity of two temporal path problems, Minimum Arrival and Best Policy, is presented for this stochastic temporal graph model.