11:00
12:00

Mikaël Rabie (IRIF)

Title: Finding a Path or a Coloring in Temporal Graphs

Abstract:

Temporal graphs are graphs whose edge set changes over time. There are lines of work consisting of adapting classical problems from static to temporal graphs.

In this talk, I will first present a new adaptation of the coloring problem in temporal graphs. In particular, there is no direct adaptation, and several definitions exist in the literature. I will present a definition motivated by mobile agents moving through time. In particular, I will restrict the coloring such that colors remain compatible through consecutive snapshots. I will provide different results depending on some restrictions on the snapshots. This is a joint work with Allen Ibiapina, Minh-Hang Nguyen, and Cléophée Robin.

I will then talk about the Canadian Traveller Problem. In static graphs, the problem consists of optimising a travel, knowing that some edges can be removed by an adversary. We know that an edge was removed only when we are at this endpoint, and we want to minimize how much the adversary can slow us down. I will present two direct adaptations of this problem in temporal graphs, and show different results depending on when we know if a temporal edge was removed. This is a joint work with Thomas Bellito, Johanne Cohen, Bruno Escoffier, and Minh-Hang Nguyen.

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

English
LaBRI 178