Distributed graph coloring in a few rounds

DOI10.1145/1993806.1993812MaRDI QIDQ2943379zbMATH OpenOpenAlexFDO

Authors Kishore Kothapalli, Sriram Pemmaraju

Publication date 11 September 2015

Published in Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmsgraph coloringoriented graphssymmetry breaking

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Distributed algorithms (68W15)

Recommendations

• Simple and near-optimal distributed coloring for sparse graphs
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Deterministic distributed vertex coloring in polylogarithmic time
• Deterministic distributed vertex coloring in polylogarithmic time
• Improved distributed \(\Delta\)-coloring

Cites work

• Almost-Everywhere Secure Computation
• Broadcasting in dynamic radio networks
• Consensus algorithms with one-bit messages
• Continuous consensus via common knowledge
• Distributed computation in dynamic networks
• Fault Tolerance in Networks of Bounded Degree
• Flooding time in edge-Markovian dynamic graphs
• Gradient clock synchronization in dynamic networks
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• scientific article; zbMATH DE number 795590 (Why is no real title available?)
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Knowledge and common knowledge in a distributed environment
• Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony
• Optimal gradient clock synchronization in dynamic networks
• Parsimonious flooding in dynamic graphs
• Perfectly secure message transmission
• Programming simultaneous actions using common knowledge
• Reaching Agreement in the Presence of Faults

Cited in

(11)

• Design patterns in beeping algorithms: examples, emulation, and analysis
• Distributed algorithms for fractional coloring
• Distributed coloring in sparse graphs with fewer colors
• Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
• Exact bounds for distributed graph colouring
• Fast Distributed Algorithms for Brooks–Vizing Colorings
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• Distributed Coloring in Sparse Graphs with Fewer Colors
• Simple and near-optimal distributed coloring for sparse graphs
• Graph coloring via degeneracy in streaming and other space-conscious models
• Brief announcement: Massively parallel ruling set made deterministic

This page was built for publication: Distributed graph coloring in a few rounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943379)