We give an improved randomized CONGEST algorithm for distance-2 coloring that uses Δ2+1 colors and runs in O(logn) rounds, improving the recent O(logΔ⋅logn)-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to O(logΔ)+2O(loglogn√).
AAAI Workshop on Information-Theoretic Causal Inference and Discovery (ITCI)
2020
2024-05-27