2026-07-20T11:15:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23071 2025-10-02T12:32:59Z ddc:004 open_access

Brief Announcement: The Shortest Temporal Exploration Problem Balev, Stefan Sanlaville, Éric Toullalan, Antoine Graph Theory Temporal Graph Temporal Graph Exploration A temporal graph is a graph for which the edge set can change from one time step to the next. This paper considers undirected temporal graphs defined over L time steps and connected at each time step. We study the Shortest Temporal Exploration Problem (STEXP) that, given the evolution of the graph, asks for a temporal walk that starts at a given vertex, moves over at most one edge at each time step, visits all the vertices, takes at most L time steps and traverses the smallest number of edges. We prove that every constantly connected temporal graph with n vertices can be explored with O(n^{1.5}) edges traversed if L is O(n^{3.5}) time steps. This result improves the upper bound of O(n²) edges when L is Ω(n²). Moreover, we study the case where the graph has a diameter bounded by a parameter k at each time step and we prove that there exists an exploration which takes O(kn²) time steps and traverses O(kn) edges. Finally, the case where the underlying graph is a cycle is studied and tight linear bounds are provided on the number of edges traversed in the worst-case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Balev and Éric Sanlaville and Antoine Toullalan 2025 Is Part Of LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2025.18 urn:nbn:de:0030-drops-230716 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.18 eng https://creativecommons.org/licenses/by/4.0/legalcode