38 citations · 178 across the 46 of their papers we have counts for
37 papers · 1 filter
No distributed quantum advantage for approximate graph coloring
Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala +7
We give an almost complete characterization of the hardness of -coloring -chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. I…
Coloring Fast with Broadcasts
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
We present an -round distributed algorithm for the -coloring problem, where each node broadcasts only one -bit message per round to its neighbors…
List Defective Colorings: Distributed Algorithms and Applications
Marc Fuchs, Fabian Kuhn
The distributed coloring problem is at the core of the area of distributed graph algorithms and it is a problem that has seen tremendous progress over the last few years. Much of t…
A Distributed Palette Sparsification Theorem
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA'19] shows that to compute a coloring of the graph, where denotes the maximum degree, it suf…
Node and Edge Averaged Complexities of Local Graph Problems
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn +1
The node-averaged complexity of a distributed algorithm running on a graph is the average over the times at which the nodes of finish their computation and commit…
Distributed Edge Coloring in Time Polylogarithmic in
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main resu…