An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
DOI10.1007/978-3-642-11476-2_25zbMATH Open1274.68683OpenAlexW1886232660MaRDI QIDQ3408183FDOQ3408183
Authors: Métivier Yves, Saheb-Djahromi Nasser, John Michael Robson, A. Zemmari 
Publication date: 24 February 2010
Published in: Structural Information and Communication Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-11476-2_25
Recommendations
- An optimal bit complexity randomized distributed MIS algorithm
- Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
- Distributed Maximal Independent Set using Small Messages
- An Improved Distributed Algorithm for Maximal Independent Set
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)
Cites Work
- Introduction to Distributed Algorithms
- The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
- Title not available (Why is that?)
- Design and Analysis of Distributed Algorithms
- Bit complexity of breaking and achieving symmetry in chains and rings
- Distributed Computing: A Locality-Sensitive Approach
- Communication Complexity
- 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
- \textsc{Maximal Independent Sets} in radio networks
- What cannot be computed locally!
- On the complexity of distributed graph coloring
- Distributed Computing
- What Can be Computed Locally?
- Distributed Systems
Cited In (8)
- Tight analysis of parallel randomized greedy MIS
- On lower bounds for the time and the bit complexity of some probabilistic distributed graph algorithms. Extended abstract
- Trading bit, message, and time complexity of distributed algorithms
- Tight bounds for MIS in multichannel radio networks
- Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
- An optimal bit complexity randomized distributed MIS algorithm
- Distributed minimum dominating set approximations in restricted families of graphs
- Luby's MIS algorithms made self-stabilizing
This page was built for publication: An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3408183)
