Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

The temporal explorer who returns to the base

Akrida, E.C. and Mertzios, G.B. and Spirakis, P.G. and Raptopoulos, C. (2021) 'The temporal explorer who returns to the base.', Journal of computer and system sciences., 120 . pp. 179-193.

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

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
Download PDF
(877Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.jcss.2021.04.001
Publisher statement:© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:06 April 2021
Date deposited:16 April 2021
Date of first online publication:15 April 2021
Date first made open access:15 April 2022

Save or Share this output

Export:
Export
Look up in GoogleScholar