Helsinki CS Theory Seminar
The seminar is a weekly series of talks on a broad scope of CS theory hosted by Helsinki Algorithms and Theory.
When
–
Where
Onsite
AS4, Maarintie 8
Speaker: Maxime Roland René Flin
Date: 22 October 2025
Time:14:15
Title: Dynamic Vertex Coloring
Abstract: In this talk, we will discuss the problem of maintaining a vertex coloring in a graph of vertices and maximum degree , subject to edge insertions and deletions. We will begin by reviewing algorithms with —or even —update time when the sequence of updates is oblivious to the decisions made by the algorithm. We then present recent advances achieving a update time against adaptive adversaries, which decide which edges to add or remove based on past decisions made by the algorithm.
Based on joint work with Magnús M. Halldórsson.
More Information about the Helsinki CS Theory Seminar is available on the event website