An optimal distributed (Δ+1)-coloring algorithm?
From MaRDI portal
Publication:5230309
DOI10.1145/3188745.3188964zbMath1427.68355arXiv1711.01361OpenAlexW2772780650MaRDI QIDQ5230309
Yi-Jun Chang, Wenzheng Li, Seth Pettie
Publication date: 22 August 2019
Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.01361
Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items (20)
Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Node and edge averaged complexities of local graph problems ⋮ A note on the network coloring game: a randomized distributed \((\Delta+1)\)-coloring algorithm ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Unnamed Item ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Improved distributed \(\Delta\)-coloring ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ A topological perspective on distributed network algorithms ⋮ Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds ⋮ Distributed Recoloring ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Distributed Spanner Approximation ⋮ Distributed coloring in sparse graphs with fewer colors ⋮ Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists
This page was built for publication: An optimal distributed (Δ+1)-coloring algorithm?
