An optimal distributed (Δ+1)-coloring algorithm?

DOI10.1145/3188745.3188964zbMath1427.68355arXiv1711.01361MaRDI 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

zbMATH Keywords

vertex coloring; distributed algorithms; local model

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C15: Coloring of graphs and hypergraphs

68W20: Randomized algorithms

68W15: Distributed algorithms

Related Items

An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model, Unnamed Item, Unnamed Item, Distributed Spanner Approximation, Network Decomposition and Distributed Derandomization (Invited Paper), Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering, Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds, Distributed Recoloring, Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs, Improved distributed algorithms for coloring interval graphs with application to multicoloring trees, A topological perspective on distributed network algorithms, Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC, Distributed Lower Bounds for Ruling Sets, Unnamed Item, Node and edge averaged complexities of local graph problems, A note on the network coloring game: a randomized distributed \((\Delta+1)\)-coloring algorithm, Improved distributed \(\Delta\)-coloring, Linial for lists, Distributed coloring in sparse graphs with fewer colors, Distributed minimum vertex coloring and maximum independent set in chordal graphs