Halldórsson, Magnús M.; Konrad, Christian
(Elsevier BV, 2020-04)
We give a distributed (1+eps)-approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O((1/eps) log* n) rounds. If nodes are aware of their interval representations, then the ...