Papers for

real-time traffic controllers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Dynamic graph coloring made faster simpler and more stable

Dynamic $(Δ+1)$-Coloring Against an Adaptive Adversary: Faster, Simpler, Worst-Case, and Bounded Recourse

Abstract: We study fully dynamic $(Δ+1)$-coloring against an adaptive adversary. Behnezhad, Rajaraman, and Wasim (SODA 2025) gave the first algorithm with $\tilde O(n^{8/9})$ amortized update time, later improved to $\tilde O(n^{2/3})$ by Flin and Halldórsson (ICALP 2025). We give a fully dynamic $(Δ+1)$-coloring algorithm with $\tilde O(\sqrt n)$ \textbf{worst-case} update time. Unlike previous algorithms, it avoids sparse-dense decompositions and relies only on elementary data structures, resulting in a short self-contained algorithm and analysis. Moreover, it avoids global recoloring, resulting in a worst-case recourse of $3$.

Mon 19 OctData Structures and Algorithms

The gist

Coloring a graph means assigning colors to connected points so no neighbors share the same color. This paper improves how fast and smoothly we can update these colors when the graph changes, even if changes depend on previous colors. The authors designed a simpler, faster method that reacts quickly without needing complex steps or big reshuffles of colors. Their method limits the number of color changes needed after each update, ensuring stability and efficiency.

Open → 2610.26182v1