Skip to main content

Research Repository

Advanced Search

The temporal explorer who returns to the base

Akrida, E.C.; Mertzios, G.B.; Spirakis, P.G.; Raptopoulos, C.

The temporal explorer who returns to the base Thumbnail


Authors

P.G. Spirakis

C. Raptopoulos



Abstract

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 exploratkion 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).

Citation

Akrida, E., Mertzios, G., Spirakis, P., & Raptopoulos, C. (2021). The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120, 179-193. https://doi.org/10.1016/j.jcss.2021.04.001

Journal Article Type Article
Acceptance Date Apr 6, 2021
Online Publication Date Apr 15, 2021
Publication Date 2021-09
Deposit Date Apr 15, 2021
Publicly Available Date Apr 15, 2022
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 120
Pages 179-193
DOI https://doi.org/10.1016/j.jcss.2021.04.001

Files





You might also like



Downloadable Citations