pipette
ENEnglish

Dynamic 3-Coloring of Bipartite Graphs with Optimal Locality

Yann Bourreau, Filippo Casagrande, Tim G\"ottlicher, Ananth Narayanan Karunattillam

Preprint

En palabras de los autores

We give a dynamic graph algorithm which maintains a 3-coloring in bipartite graphs under edge insertions such that the coloring only changes within a radius of around an inserted edge. In the context of locality theory in distributed graph algorithms, this gives an upper bound on the locality under the dynamic-LOCAL model. Our bound on the locality is tight, as the problem admits a matching lower bound in the stronger online-LOCAL model, by a result of Chang et al. [PODC 2024]. Thus, our result closes the gap between dynamic and online locality of this problem.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 18 pages, 2 figures