Improved exploration of temporal graphs

Prelegent(ci)

Clément Rambaud

Afiliacja

Université Côte d'Azur

Język referatu

angielski

Termin

15 maja 2026 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

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.

---