Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
From MaRDI portal
Publication:342718
DOI10.1016/j.ic.2016.09.006zbMath1353.68297OpenAlexW2521555281MaRDI QIDQ342718
John Michael Robson, Akka Zemmari, Yves Métivier
Publication date: 18 November 2016
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2016.09.006
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
- An optimal bit complexity randomized distributed MIS algorithm
- About randomised distributed graph colouring and graph partition algorithms
- Simple distributed \(\Delta+1\)-coloring of graphs
- Combinatorial algorithms for distributed graph coloring
- Distributed graph coloring in a few rounds
- Trading Bit, Message, and Time Complexity of Distributed Algorithms
- Deploying Wireless Networks with Beeps
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- Introduction to Distributed Algorithms
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Stone age distributed computing
- Feedback from nature
- Maximal independent sets in radio networks
- On the complexity of distributed graph coloring
- Distributed Computing
This page was built for publication: Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
