Distributed (∆+1)-coloring in sublogarithmic rounds

DOI10.1145/2897518.2897533zbMath1376.68160arXiv1603.01486OpenAlexW2963714020MaRDI QIDQ5361852

No author found.

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1603.01486

zbMATH Keywords

graph coloringsymmetry breakingdistributed algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (16)

What can be sampled locally? ⋮ Improved deterministic distributed matching via rounding ⋮ Node and edge averaged complexities of local graph problems ⋮ Unnamed Item ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ Improved distributed \(\Delta\)-coloring ⋮ Unnamed Item ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ A topological perspective on distributed network algorithms ⋮ Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Distributed Spanner Approximation ⋮ Distributed coloring in sparse graphs with fewer colors

This page was built for publication: Distributed (∆+1)-coloring in sublogarithmic rounds