Dr Eleni Akrida eleni.akrida@durham.ac.uk
Associate Professor
The temporal explorer who returns to the base
Akrida, E.C.; Mertzios, G.B.; Spirakis, P.G.; Raptopoulos, C.
Authors
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
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
Accepted Journal Article
(898 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright 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/
You might also like
Narrowing and Stretching: Addressing the Challenge of Multi-track Programming
(2022)
Conference Proceeding
Connected Subgraph Defense Games
(2021)
Journal Article
How fast can we reach a target vertex in stochastic temporal graphs?
(2020)
Journal Article
Connected Subgraph Defense Games
(2019)
Book Chapter
Temporal vertex cover with a sliding time window
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search