An optimal bit complexity randomized distributed MIS algorithm
From MaRDI portal
Publication:658666
DOI10.1007/s00446-010-0121-5zbMath1231.68277WikidataQ59409896 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
68R10: Graph theory (including graph drawing) in computer science
68M14: Distributed systems
68W20: Randomized algorithms
68W15: Distributed algorithms
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!