Akrida, Eleni C, Mertzios, George B, Spirakis, Paul G 
ORCID: 0000-0001-5396-3749 and Raptopoulos, Christoforos
(2021)
The temporal explorer who returns to the base.
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 120.
pp. 179-193.
|
Text
REVISED_JCSS_20_exploration_manuscript.pdf - Author Accepted Manuscript Download (432kB) | Preview |
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 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).
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Temporal networks, Exploration, Random input, Edge availability |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 08 Apr 2021 07:55 |
| Last Modified: | 18 Jan 2023 22:53 |
| DOI: | 10.1016/j.jcss.2021.04.001 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3118631 |
Dimensions
Dimensions
