2020/05/13 by Halldorsson, Magnus M., Kuhn, Fabian, Maus, Yannic
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2005.06528
We give efficient randomized and deterministic distributed algorithms for computing a distance-2 vertex coloring of a graph G in the CONGEST model. In particular, if Δ is the maximum degree of G, we show that there is a randomized CONGEST model algorithm to compute a distance-2 coloring of G with Δ2+1 colors in O(logΔ⋅log n) rounds. Further if the number of colors is slightly increased to (1+ε)Δ2 for some ε>1/\rm polylog(n), we show that it is even possible to compute a distance-2 coloring deterministically in polylog(n) time in the CONGEST model. Finally, we give a O(Δ2 + log^* n)-round deterministic CONGEST algorithm to compute distance-2 coloring with Δ2+1 colors.