On temporal graph exploration
On temporal graph exploration
复制标题
关于时间图探索
DOI：
10.1016/j.jcss.2021.01.005
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Erlebach T
中科院分区：
文献类型：
--
作者：
Erlebach T
时间图探索问题TEXP是计算时间图的最重要的探索时间表的问题，即从给定的起始节点开始，访问图的所有节点，并且具有最小到达时间的时间行走。在本文的第一和第二部分中，我们只考虑在每个时间步连接的无向时间图。对于这样的时间图与n个节点，我们证明了它是NP-困难的近似TEXP比O（n 1-ε），每ε> 0，并提出了几个解决方案，为特殊的图类。在本文的第三部分中，我们考虑设置在未来的时间步长的图形是未知的。我们表明，m-边的时间图，定期目前的边缘和概率目前的边缘可以探索在线O（m）的时间步长和O（m log n）的时间步长，分别具有高概率。
The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, ie, 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 and second 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− ε) for every ε> 0 and present several solutions for special graph classes. In the third part of the paper, we consider settings where the graphs in future time steps are not known. We 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.