A distributed palette sparsification theorem
The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA'19] shows
that to compute a Δ+ 1 coloring of the graph, where Δ denotes the maximum degree, it …
that to compute a Δ+ 1 coloring of the graph, where Δ denotes the maximum degree, it …
Simpler and More General Distributed Coloring Based on Simple List Defective Coloring Algorithms
In this paper, we give list coloring variants of simple iterative defective coloring algorithms.
Formally, in a list defective coloring instance, each node $ v $ of a graph is given a list $ L_v …
Formally, in a list defective coloring instance, each node $ v $ of a graph is given a list $ L_v …
Fast coloring despite congested relays
M Flin, MM Halldórsson, A Nolin - arXiv preprint arXiv:2308.01359, 2023 - arxiv.org
We provide a $ O (\log^ 6\log n) $-round randomized algorithm for distance-2 coloring in
CONGEST with $\Delta^ 2+ 1$ colors. For $\Delta\gg\operatorname {poly}\log n $, this …
CONGEST with $\Delta^ 2+ 1$ colors. For $\Delta\gg\operatorname {poly}\log n $, this …
Simple Sublinear Algorithms for (Δ+ 1) Vertex Coloring via Asymmetric Palette Sparsification
S Assadi, H Yazdanyar - 2025 Symposium on Simplicity in Algorithms (SOSA), 2025 - SIAM
The palette sparsification theorem (PST) of Assadi, Chen, and Khanna (SODA 2019) states
that in every graph G with maximum degree Δ, sampling a list of O (log n) colors from {1 …
that in every graph G with maximum degree Δ, sampling a list of O (log n) colors from {1 …
Decentralized distributed graph coloring II: degree+ 1-coloring virtual graphs
M Flin, MM Halldórsson, A Nolin - arXiv preprint arXiv:2408.11041, 2024 - arxiv.org
Graph coloring is fundamental to distributed computing. We give the first general treatment
of the coloring of virtual graphs, where the graph $ H $ to be colored is locally embedded …
of the coloring of virtual graphs, where the graph $ H $ to be colored is locally embedded …
Decentralized Distributed Graph Coloring: Cluster Graphs
M Flin, MM Halldorsson, A Nolin - arXiv preprint arXiv:2405.07725, 2024 - arxiv.org
Graph coloring is fundamental to distributed computing. We give an ultrafast distributed
algorithm for coloring cluster graphs. These graphs are obtained from the underlying …
algorithm for coloring cluster graphs. These graphs are obtained from the underlying …
An Efficient and Robust Distributed Vertex Coloring Algorithm in Wireless Networks
The distributed vertex coloring is one of the most intensively studied problem in graph theory
with many applications in computer networks. We propose a deterministic distributed …
with many applications in computer networks. We propose a deterministic distributed …