Parameterised temporal exploration problems
Parameterised temporal exploration problems
复制标题
参数化时间探索问题
DOI：
10.1016/j.jcss.2023.01.003
复制
发表时间：
2023
影响因子：
1.1
通讯作者：
Erlebach T
中科院分区：
文献类型：
--
作者：
Erlebach T
我们研究的固定参数的易处理性的问题，决定是否一个给定的时间图承认一个时间的行走，访问所有顶点（时间探索），或在某些变体中，某个子集的顶点。在严格的变体中，必须以严格递增的时间步长遍历边;在非严格的变体中，在每个时间步长中可以遍历任何数量的边。对于这两种变体，我们给出FPT算法，用于找到访问给定顶点集X的时间行走，参数化为|X|以及用于找到访问至少k个不同顶点的时间行走，由k参数化。我们还显示了W [2]-硬度的一套版本的时间探索。对于非严格的变体，我们给出了一个FPT算法的时间探索参数化的生命周期，并表明，时间探索可以解决在多项式时间，如果在每个时间步的图有最多两个连接组件。
We study the fixed-parameter tractability of the problem of deciding whether a given temporal graph admits a temporal walk that visits all vertices (temporal exploration) or, in some variants, a certain subset of the vertices. In the strict variant, edges must be traversed in strictly increasing timesteps; in the non-strict variant, any number of edges can be traversed in each timestep. For both variants, we give FPT algorithms for finding a temporal walk that visits a given set X of vertices, parameterised by| X|, and for finding a temporal walk that visits at least k distinct vertices, parameterised by k. We also show W [2]-hardness for a set version of temporal exploration. For the non-strict variant, we give an FPT algorithm for temporal exploration parameterised by the lifetime, and show that temporal exploration can be solved in polynomial time if the graph in each timestep has at most two connected components.