Distributed deterministic edge coloring using bounded neighborhood independence
From MaRDI portal
Publication:5892122
DOI10.1145/1993806.1993825zbMath1321.68377OpenAlexW2011894656MaRDI QIDQ5892122
Leonid Barenboim, Michael Elkin
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.1993825
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Distributed algorithms (68W15)
Related Items (3)
Improved distributed degree splitting and edge coloring ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
Cites Work
- Unnamed Item
- 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
This page was built for publication: Distributed deterministic edge coloring using bounded neighborhood independence