Improved exploration of temporal graphs

Speaker(s)

Clément Rambaud

Affiliation

Université Côte d'Azur

Language of the talk

English

Date

May 15, 2026, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

A temporal graph is a sequence of graphs (G_t)_t on the same vertex set of size n. The temporal exploration problem asks for the length of the shortest sequence of vertices that starts at a given vertex, visits every vertex, and at each time step t either stays at the current vertex or moves to an adjacent vertex in G_t. Bounds on the length of a shortest temporal exploration have been investigated extensively. Perhaps the most fundamental case is when each graph G_t is connected and has bounded maximum degree. In this setting, Erlebach, Kammer, Luo, Sajenko, and Spooner [ICALP 2019] showed that there exists an exploration of G in O(n^{7/4}) time steps. We significantly improve this bound by showing that O(n^{3/2} \sqrt{log n}) time steps suffice.
In fact, we deduce this result from a much more general statement that also improves known bounds for the case where the underlying graph is planar, or more generally has bounded degeneracy.

This is joint work with Paul Bastide, Carla Groenland, and Lukas Michel.

---