Faster Exploration of Degree-Bounded Temporal Graphs
Faster Exploration of Degree-Bounded Temporal Graphs
复制标题
更快地探索有界时间图
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Jakob T. Spooner
中科院分区：
文献类型：
--
作者：
T. Erlebach;Jakob T. Spooner
临时图可以视为由离散时间步长索引的静态图。探索问题（TEXP）：作为输入，临时图g，我们的任务是计算探索时间表（即临时步行，访问g中的所有顶点），以便时间步行到达最后一个未访问的顶点的步骤是最小化的（我们将这个时间步骤称为到达时间） ，以前已经证明存在一个无限的临时图家族，任何探索时间表都已经到达时间ω（n2），使得这些界限紧密实例。我们考虑了TEXP的限制实例，其中给出的临时图是每个时间步骤d的最大程度d； o（d log d·n2 logn）当d作为n的某些函数时，计算的数学→图形算法。
A temporal graph can be viewed as a sequence of static graphs indexed by discrete time steps. The vertex set of each graph in the sequence remains the same; however, the edge sets are allowed to differ. A natural problem on temporal graphs is the Temporal Exploration problem (TEXP): given, as input, a temporal graph G of order n, we are tasked with computing an exploration schedule (i.e., a temporal walk that visits all vertices in G), such that the time step at which the walk arrives at the last unvisited vertex is minimised (we refer to this time step as the arrival time). It can be easily shown that general temporal graphs admit exploration schedules with arrival time no greater than O(n2). Moreover, it has been shown previously that there exists an infinite family of temporal graphs for which any exploration schedule has arrival time Ω(n2), making these bounds tight for general TEXP instances. We consider restricted instances of TEXP, in which the temporal graph given as input is, in every time step, of maximum degree d; we show an O( n 2 logn ) bound on the arrival time when d is constant, and an O(d log d · n2 logn ) bound when d is given as some function of n. 2012 ACM Subject Classification Mathematics of computing → Graph algorithms