Randomised distributed MIS and colouring algorithms for rings with oriented edges in O( n) bit rounds

DOI10.1016/J.IC.2016.09.006MaRDI QIDQ342718zbMATH OpenOpenAlexFDO

Authors Yves Métivier, John Michael Robson, A. Zemmari

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

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• On the time and the bit complexity of distributed randomised anonymous ring colouring
• Nearly optimal distributed edge coloring in O(log log n) rounds
• Fast randomized algorithms for distributed edge coloring (extended abstract)
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• scientific article; zbMATH DE number 1875427
• A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds

Cites work

• \textsc{Maximal Independent Sets} in radio networks
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• About randomised distributed graph colouring and graph partition algorithms
• An optimal bit complexity randomized distributed MIS algorithm
• Combinatorial algorithms for distributed graph coloring
• Deploying wireless networks with beeps
• Distributed Computing
• Distributed Computing: A Locality-Sensitive Approach
• Distributed graph coloring in a few rounds
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Feedback from nature, an optimal distributed algorithm for \textsc{Maximal Independent Set} selection
• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• Introduction to Distributed Algorithms
• Locality in Distributed Graph Algorithms
• On the complexity of distributed graph coloring
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• Simple distributed +1-coloring of graphs
• Stone age distributed computing
• Trading bit, message, and time complexity of distributed algorithms

Cited in

(3)

• On the time and the bit complexity of distributed randomised anonymous ring colouring
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• Distributed acyclic orientation of asynchronous anonymous networks

This page was built for publication: Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342718)