11:00
12:00

Antoine Toullalan (LITIS)

Title: The Shortest Temporal Exploration Problem

Abstract:

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²) time steps. This result improves the upper bound of O(n²) edges for an exploration provided by the upper bound of time steps for an exploration which is also O(n²). 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(n²) 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≥2n-3.

The talk will be in English

https://algodist.labri.fr/index.php/Main/GT

LaBRI salle 178 - lien visio https://webconf.u-bordeaux.fr/b/arn-4tr-7gp