Distributed graph coloring in a few rounds

DOI10.1145/1993806.1993812zbMATH Open1321.68476OpenAlexW2091919917MaRDI QIDQ2943379FDOQ2943379

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

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

zbMATH Keywords

distributed algorithmsgraph coloringsymmetry breakingoriented graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Simple and near-optimal distributed coloring for sparse graphs
• Distributed algorithms for fractional coloring
• Distributed coloring in sparse graphs with fewer colors
• Exact bounds for distributed graph colouring
• Design patterns in beeping algorithms: examples, emulation, and analysis
• Faster Deterministic Distributed Coloring Through Recursive List 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
• Fast Distributed Algorithms for Brooks–Vizing Colorings

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)