Distributed recoloring of interval and chordal graphs

Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikael Rabie.

OPODIS 2021: Conference on Principles of Distributed Systems, 13-15 December 2021, Strasbourg, France.


Open access publisher's version arxiv version Video at OPODIS 2021 (by Mikaël)


One of the fundamental and most-studied algorithmic problems in distributed computing on networks is graph coloring, both in bounded-degree and in general graphs. Recently, the study of this problem has been extended in two directions. First, the problem of recoloring, that is computing an efficient transformation between two given colorings (instead of computing a new coloring), has been considered, both to model radio network updates, and as a useful subroutine for coloring. Second, as it appears that general graphs and bounded-degree graphs do not model real networks very well (with, respectively, pathological worst-case topologies and too strong assumptions), coloring has been studied in more specific graph classes. In this paper, we study the intersection of these two directions: distributed recoloring in two relevant graph classes, interval and chordal graphs.


Mikaël presented the paper at OPODIS.