An optimal bit complexity randomized distributed MIS algorithm

DOI10.1007/s00446-010-0121-5zbMath1231.68277OpenAlexW2149652607WikidataQ59409896 ScholiaQ59409896MaRDI QIDQ658666

John Michael Robson, Yves Métivier, Akka Zemmari, Nasser Saheb-Djahromi

Publication date: 6 February 2012

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-010-0121-5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (12)

Randomized OBDD-based graph algorithms ⋮ Design patterns in beeping algorithms: examples, emulation, and analysis ⋮ Randomized OBDD-Based Graph Algorithms ⋮ Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds ⋮ Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings ⋮ Find Your Place: Simple Distributed Algorithms for Community Detection ⋮ Beeping a maximal independent set ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ On the Microscopic View of Time and Messages ⋮ Simple and local independent set approximation ⋮ Noisy beeping networks

Cites Work

• Unnamed Item
• Unnamed Item
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• Coloring unstructured radio networks
• Distributed Systems
• Design and Analysis of Distributed Algorithms
• Bit complexity of breaking and achieving symmetry in chains and rings
• 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
• What Can be Computed Locally?
• Communication Complexity
• On the complexity of distributed graph coloring
• Distributed Computing
• What cannot be computed locally!

This page was built for publication: An optimal bit complexity randomized distributed MIS algorithm