License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2021.19
URN: urn:nbn:de:0030-drops-157941
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15794/
Bousquet, Nicolas ;
Feuilloley, Laurent ;
Heinrich, Marc ;
Rabie, Mikaël
Distributed Recoloring of Interval and Chordal Graphs
Abstract
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.
More formally, the question of recoloring a graph is as follows: we are given a network, an input coloring α and a target coloring β, and we want to find a schedule of colorings to reach β starting from α. In a distributed setting, the schedule needs to be found within the LOCAL model, where nodes communicate with their direct neighbors synchronously. The question we want to answer is: how many rounds of communication {are} needed to produce a schedule, and what is the length of this schedule?
In the case of interval and chordal graphs, we prove that, if we have less than 2ω colors, ω being the size of the largest clique, extra colors will be needed in the intermediate colorings. For interval graphs, we produce a schedule after O(poly(Δ)log*n) rounds of communication, and for chordal graphs, we need O(ω²Δ²log n) rounds to get one.
Our techniques also improve classic coloring algorithms. Namely, we get ω+1-colorings of interval graphs in O(ωlog*n) rounds and of chordal graphs in O(ωlog n) rounds, which improves on previous known algorithms that use ω+2 colors for the same running times.
BibTeX - Entry
@InProceedings{bousquet_et_al:LIPIcs.OPODIS.2021.19,
author = {Bousquet, Nicolas and Feuilloley, Laurent and Heinrich, Marc and Rabie, Mika\"{e}l},
title = {{Distributed Recoloring of Interval and Chordal Graphs}},
booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
pages = {19:1--19:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-219-8},
ISSN = {1868-8969},
year = {2022},
volume = {217},
editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15794},
URN = {urn:nbn:de:0030-drops-157941},
doi = {10.4230/LIPIcs.OPODIS.2021.19},
annote = {Keywords: Distributed coloring, distributed recoloring, interval graphs, chordal graphs, intersection graphs}
}
|
Keywords: |
|
Distributed coloring, distributed recoloring, interval graphs, chordal graphs, intersection graphs |
|
Collection: |
|
25th International Conference on Principles of Distributed Systems (OPODIS 2021) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.02.2022 |
