Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering

DOI10.1137/19M1249527zbMath1443.68214MaRDI QIDQ5112251

Yi-Jun Chang, Seth Pettie, Wenzheng Li

Publication date: 28 May 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

graph coloring; distributed algorithm; local model

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

68W15: Distributed algorithms