Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks

DOI10.1145/2979675zbMath1426.68290OpenAlexW2554518674MaRDI QIDQ3177822

Leonid Barenboim

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2979675

zbMATH Keywords

partitionspolynomialscoloringdistributed algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Related Items (8)

What can be sampled locally? ⋮ Distributed coloring of hypergraphs ⋮ Almost global problems in the LOCAL model ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ Almost global problems in the LOCAL model ⋮ Local mending ⋮ Linial for lists

This page was built for publication: Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks