Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds

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

Mathematics Subject Classification ID

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