A temporal graph is a graph in which the edge set can change from one time step to the next. The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. In the first part of the paper, we consider only undirected temporal graphs that are connected at each time step. For such temporal graphs with $n$ nodes, we show that it is \NP-hard to approximate TEXP with ratio $O(n^{1-\varepsilon})$ for every $\varepsilon>0$. We also provide an explicit construction of temporal graphs that require $\Theta(n^2)$ time steps to be explored. In the second part of the paper, we still consider temporal graphs that are connected in each time step, but we assume that the underlying graph (i.e. the graph that contains all edges that are present in the temporal graph in at least one time step) belongs to a specific class of graphs. Among other results, we show that temporal graphs can be explored in $O(n^{1.5}k^{1.5}\log n)$ time steps if the underlying graph has treewidth $k$, in $O(n^{1.8}\log n)$ time steps if the underlying graph is planar, and in $O(n\log^3 n)$ time steps if the underlying graph is a $2\times n$ grid. In the third part of the paper, we consider settings where the graphs in future time steps are not known and the exploration schedule is constructed online. We replace the connectedness assumption by a weaker assumption and show that $m$-edge temporal graphs with regularly present edges and with probabilistically present edges can be explored online in $O(m)$ time steps and $O(m \log n)$ time steps with high probability, respectively. We finally show that the latter result can be used to obtain a distributed algorithm for the gossiping problem in random temporal graphs.
翻译:时间图是一个图形, 其边缘可以从一个时间级向下一个时间级变化。 时间图探索问题 TEXP 是一个问题, 如何计算一个时间级图最首要的勘探时间表, 即从一个给定的启动节点开始的时间行走, 访问图形的所有节点, 并有最小的到达时间。 在文件的第一部分, 我们仅考虑每个时间级连接的非方向时间级图。 对于使用 $n 节点的这种时间级图, 我们显示的是\NNNNN- 美元 的硬度, 大约TEXP, 比率为 $( n_1-\ varepsilon) 。 每张时间级图中, 每张时间级图中, 以 $ $ 美元 。 以n_ 平面值 平面图中包含所有边缘, 以 $ 美元 美元 。 以时间级图中显示的是 $ 。 以 美元 时间级图中的步骤, 以 =__ 向一个特定的脚级 。 如果我们在一个时间级 日期级 底级 显示的是, 美元 底的脚级的脚级的脚级的脚级的脚级 。