The temporal explorer who returns to the base
The temporal explorer who returns to the base
复制标题
返回基地的时空探索者
DOI：
10.1016/j.jcss.2021.04.001
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Akrida E
中科院分区：
文献类型：
--
作者：
Akrida E
我们在这里研究的问题，探索一个时间图时，底层图是一个星星。时间星星中的探索问题的目的是找到一个时间行走，该行走开始和结束于星星的中心，并访问所有的叶子。我们提出了一个系统的研究这个问题的计算复杂性，取决于每个边缘可以存在于图中的时间点的数量k。我们区分决策版本StarExp（k），询问是否存在完整的探索，以及最大化版本MaxStarExp（k），要求探索最大可能数量的边缘。我们在复杂性方面充分表征MaxStarExp（k）。我们还部分地刻画了StarExp（k），表明当k< 4时它在P中，但当k> 5时它是NP完全的。最后，我们部分描述了“随机”的时间星类，渐近几乎肯定，是实例和非实例StarExp（k）。
We study here the problem of exploring a temporal graph when the underlying graph is a star. The aim of the exploration problem in a temporal star is finding a temporal walk which starts and finishes at the center of the star, and visits all leaves. We present a systematic study of the computational complexity of this problem, depending on the number k of time points where each edge can be present in the graph. We distinguish between the decision version StarExp (k), asking whether a complete exploration exists, and the maximization version MaxStarExp (k), asking for an exploration of the greatest possible number of edges. We fully characterize MaxStarExp (k) in terms of complexity. We also partially characterize StarExp (k), showing that it is in P for k< 4, but is NP-complete, for every k> 5. Finally, we partially characterize classes of “random” temporal stars which are, asymptotically almost surely, yes-instances and no-instances for StarExp (k).
登录
查看更多内容
具有随机链接可用性的临时网络：快速网络的情况
影响因子：
3.8
作者：
Akrida E
通讯作者：
Akrida E
非对称旅行商问题的常因子逼近算法
DOI：
10.1145/3188745.3188824
发表时间：
2018
期刊：
--
影响因子：
--
作者：
Svensson O
通讯作者：
Svensson O
关于探索小路径宽度的时间图
DOI：
--
发表时间：
2018
期刊：
arXiv.org
影响因子：
--
作者：
H. Bodlaender;Tom C. van der Zanden
通讯作者：
Tom C. van der Zanden
DOI：
10.1007/978-3-319-28472-9_11
发表时间：
2015-09
期刊：
--
影响因子：
--
作者：
Eleni C. Akrida;P. Spirakis
通讯作者：
Eleni C. Akrida;P. Spirakis
基于Cactuses的常连通动态图探索
DOI：
--
发表时间：
2014
期刊：
Colloquium on Structural Information & Communication Complexity
影响因子：
--
作者：
D. Ilcinkas;R. Klasing;A. Wade
通讯作者：
A. Wade