Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.06652 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915234538586112 |
|---|---|
| author | Balev, Stefan Sanlaville, Éric Toullalan, Antoine |
| author_facet | Balev, Stefan Sanlaville, Éric Toullalan, Antoine |
| contents | 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 all 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 within O(n 3.5 ) time steps. This result improves the upper bound of O(n 2 ) edges for an exploration provided by the upper bound of time steps for an exploration which is also O(n 2 ). Morever, 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 2 ) time steps and traverses O(kn) edges. Finally, the case where the underlying graph is a cycle is studied and tight bounds are provided on the number of edges traversed in the worst-case if L $\ge$ 2n -3. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06652 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Shortest Temporal Exploration Problem Balev, Stefan Sanlaville, Éric Toullalan, Antoine Optimization and Control 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 all 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 within O(n 3.5 ) time steps. This result improves the upper bound of O(n 2 ) edges for an exploration provided by the upper bound of time steps for an exploration which is also O(n 2 ). Morever, 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 2 ) time steps and traverses O(kn) edges. Finally, the case where the underlying graph is a cycle is studied and tight bounds are provided on the number of edges traversed in the worst-case if L $\ge$ 2n -3. |
| title | The Shortest Temporal Exploration Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2504.06652 |