If you are interested in graph colouring, and specifically in distributed algorithms for that classic problem, I strongly recommend the recent paper posted by Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin and Tigran Tonoyan. (For the record, three of the authors work, or have worked, in my department at Reykjavik University, so I am biased.)
The above-mentioned paper addresses the problem of finding a proper colouring of a graph when each node v has a palette of degree(v)+1 colours at its disposal. The paper resolves an open problem in distributed colouring and simplifies known results in doing so. As a byproduct of their results, the authors obtain improved streaming and sub-linear time algorithms. See the paper for much more information on the context for this result and the technical details.
Congratulations to the authors!
No comments:
Post a Comment