An optimal distributed (Δ+1)-coloring algorithm?
From MaRDI portal
Publication:5230309
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
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