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

DOI10.1145/2767386.2767410zbMath1333.68202OpenAlexW2163371823MaRDI QIDQ2796270

Leonid Barenboim

Publication date: 23 March 2016

Published in: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

partitionspolynomialscoloringdistributed algorithms

Mathematics Subject Classification ID

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

Related Items (6)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Fast Distributed Approximation for Max-Cut ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Distributed Recoloring ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs

Cites Work

• Memorization and Association on a Realistic Neural Model
• Unnamed Item

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