Distributed graph coloring in a few rounds
From MaRDI portal
Publication:2943379
DOI10.1145/1993806.1993812zbMath1321.68476OpenAlexW2091919917MaRDI QIDQ2943379
Kishore Kothapalli, Sriram V. 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
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Distributed algorithms (68W15)
Related Items
Design patterns in beeping algorithms: examples, emulation, and analysis, Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
Cites Work
- Gradient clock synchronization in dynamic networks
- Consensus algorithms with one-bit messages
- Knowledge and common knowledge in a Byzantine environment: Crash failures
- Broadcasting in dynamic radio networks
- Programming simultaneous actions using common knowledge
- Continuous consensus via common knowledge
- Distributed computation in dynamic networks
- Flooding time in edge-Markovian dynamic graphs
- Knowledge and common knowledge in a distributed environment
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony
- Fault Tolerance in Networks of Bounded Degree
- Reaching Agreement in the Presence of Faults
- Perfectly secure message transmission
- Parsimonious flooding in dynamic graphs
- Optimal gradient clock synchronization in dynamic networks
- Almost-Everywhere Secure Computation
- Unnamed Item
