Deterministic Distributed Vertex Coloring in Polylogarithmic Time

DOI10.1145/2027216.2027221zbMath1281.68164OpenAlexW2065826935MaRDI QIDQ5395667

Michael Elkin, Leonid Barenboim

Publication date: 17 February 2014

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.590.5207

zbMATH Keywords

arboricitypartial orientationarbdefective coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Distributed independent sets in interval and segment intersection graphs ⋮ Distributed algorithms for random graphs ⋮ What can be sampled locally? ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Locality and checkability in wait-free computing ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Unnamed Item ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ Distributed backup placement ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists

This page was built for publication: Deterministic Distributed Vertex Coloring in Polylogarithmic Time